Рекурсия и большой O
Я сделал быстрый алгоритм для вашего примера. Индекс начинается с нуля, поэтому вы должны пройти 0, если вам нужен первый элемент. Вы можете изменить символ разделителя или предоставить его в качестве аргумента.
Краткое объяснение: мы перебираем все символы строки и пропускаем все элементы, пока не попадем в запрошенный. После этого мы находим следующий разделитель и возвращаем часть целой строки или возвращаем остаток строки, если не находим разделителей.
public static string GetItemByIndex(string line, int index)
{
for (var i = 0; i < line.Length; i++)
{
if (index == 0)
{
for (int j = i; j < line.Length; j++)
{
if (line[j] == ',')
{
return line.Substring(i, j - i);
}
}
return line.Substring(i, line.Length - i);
}
if (line[i] == ',' && index != 0)
{
index--;
}
}
return null;
}
7 ответов
Существует несколько различных способов решить повторения: замена, дерево повторения и основная теорема. Основная теорема не будет работать в случае, потому что это не соответствует основной форме теоремы.
Вы могли использовать другие два метода, но самый легкий путь к этой проблеме состоит в том, чтобы решить его многократно.
T (n) = 2T (n-1) + 1
T (n) = 4T (n-2) + 2 + 1
T (n) = 8T (n-3) + 4 + 2 + 1
T (n) =...
Видеть шаблон?
T (n) = 2n-1⋅T (1) + 2n-2 + 2n-3 +... + 1
T (n) = 2n-1⋅2 + 2n-2 + 2n-3 +... + 1
T (n) = 2n + 2n-2 + 2n-3 +... + 1
Поэтому связанным самым трудным является Θ (2n).
Я думаю, что Вы неправильно поняли вопрос немного. Это не спрашивает Вас, сколько времени это взяло бы для решения повторения. Это спрашивает, каково большое-O (связанное асимптотическое) самого решения.
То, что необходимо сделать, должно предложить закрытое решение для формы, т.е. нерекурсивную формулу для T (n), и затем определить, каково большое-O из того выражения.
Вопрос просит большую о нотацию для решения повторения, не стоимость вычисления повторение.
Другими словами: повторение производит:
1 -> 2
2 -> 5
3 -> 11
4 -> 23
5 -> 47
Какая большая о нотация лучше всего описывает последовательность 2, 5, 11, 23, 47...
Корректный способ решить, который должен решить уравнения повторения.
Я думаю, что это будет экспоненциально. Каждый инкремент к n делает значение, чтобы быть вдвое более большим.
T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...
T (x) было бы время выполнения следующей программы (например):
def fn(x):
if (x == 1):
return # a constant time
# do the calculation for n - 1 twice
fn(x - 1)
fn(x - 1)
Я думаю, что это будет экспоненциально. Каждый инкремент к n приносит вдвое больше вычисления.
Нет, это не делает. Вполне наоборот:
Полагайте, что для n повторений, мы получаем время выполнения R. Затем для n + 1 повторение мы доберемся точно R + 1.
Таким образом темп роста является постоянным, и общее время выполнения действительно O (n).
Однако я думаю, что предположение Dima о вопросе является правильным, хотя его решение является чрезмерно сложным:
То, что необходимо сделать, должно предложить закрытое решение для формы, т.е. нерекурсивную формулу для T (n), и затем определить, каково большое-O из того выражения.
Достаточно исследовать относительный размер T (n) и T (n + 1) повторения и определить относительный темп роста. Сумма, очевидно, удваивается, который непосредственно дает асимптотический рост.
Прежде всего все четыре ответа хуже, чем O (n)... O (n*log n) более сложно, чем простой O (n). Что больше: 8 или 8 * 3, 16 или 16 * 4, и т.д...
По фактическому вопросу. Общее решение может, очевидно, быть решено в постоянное время, если Вы не делаете рекурсии
(T (n) = 2^ (n - 1) + 2^ (n) - 1), таким образом, это не то, что они спрашивают.
И как Вы видите, если мы пишем рекурсивный код:
int T( int N )
{
if (N == 1) return 2;
return( 2*T(N-1) + 1);
}
Это, очевидно, O (n).
Так, это, кажется, плохо сформулированный вопрос, и они, вероятно, спрашивают Вас рост самой функции, не сложность кода. Это 2^n. Теперь пойдите, делают остальную часть Вашей домашней работы... и учатся на O (n *, регистрируют n),
Вычисления закрытого решения для формы рекурсии легки. Контролем Вы предполагаете, что решение
T(n) = 3*2^(n-1) - 1
Затем Вы доказываете индукцией, что это - действительно решение. Основной случай:
T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.
Индукция:
Suppose T(n) = 3*2^(n-1) - 1. Then T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.
где первое равенство происходит от определения повторения и второго от индуктивной гипотезы. ЧТО И ТРЕБОВАЛОСЬ ДОКАЗАТЬ.
3*2^ (n-1) - 1 ясно Тета (2^n), следовательно правильный ответ является третьим.
Людям, которые ответили на O (n): Я не мог согласиться больше с Dima. Проблема не просит, чтобы самая трудная верхняя граница к вычислительной сложности алгоритма вычислила T (n) (который был бы теперь O (1), так как его закрытая форма была обеспечена). Проблема просит самую трудную верхнюю границу на T (n) самом, и это - экспоненциальное.