Рекурсия и большой O

Я работаю над недавней домашней работой по компьютерным наукам, включающей рекурсию и запись большого числа O. Я считаю, что я это хорошо понимаю (конечно, не совсем так!) Но есть, в частности, один вопрос, который дает мне больше всего проблем. Странно то, что, глядя на него, он выглядит как самый простой в домашней работе.

Обеспечьте наилучшую скорость роста, используя большое значение для решения следующего рецидива?

T (1) = 2

T (n) = 2T (n - 1) + 1 при n > 1

И выбор:

O (n log n)
О (п ^ 2)
О (2 ^ п)
О (п ^ п)

Я понимаю, что большой O работает как верхняя граница, чтобы описать наибольшее количество вычислений или максимальное время выполнения этой программы или процесса. Я чувствую, что эта конкретная рекурсия должна быть O (n), так как, самое большее, рекурсия происходит только один раз для каждого значения n. Поскольку n недоступно, оно либо лучше, чем O (nlogn), или, что еще хуже, является тремя другими параметрами.

Итак, мой вопрос: почему это не O (n)?

Ответ 1

Существует несколько способов решения повторений: замена, рекуррентное дерево и теорема о мастер-классе. Теорема Мастера не будет работать в этом случае, поскольку она не соответствует форме основной теоремы.

Вы можете использовать два других метода, но самый простой способ решить эту проблему - итеративно.

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) = 2 ^n-1 ⋅T (1) + 2 ^n-2 + 2 ^n-3 +... + 1
T (n) = 2 ^n-1 ⋅2 + 2 ^n-2 + 2 ^n-3 +... + 1
T (n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 +... + 1

Следовательно, самая узкая оценка Θ (2 ⁿ).

Ответ 2

Я думаю, вы неправильно поняли этот вопрос. Он не спрашивает вас, сколько времени потребуется для решения проблемы. Он задает вопрос о том, что такое большая -о (асимптотическая оценка) самого решения.

Что вам нужно сделать, так это придумать решение закрытой формы, т.е. е. нерекурсивную формулу для T (n), а затем определить, что такое big-O этого выражения.

Ответ 3

Я думаю, что это будет экспоненциально. Каждое приращение до 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)

Ответ 4

Вопрос заключается в том, что для принятия решения о повторении требуется большая нотация, а не стоимость вычисления повторения.

Поставьте другой путь: рекуррентность производит:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

Какая большая нотация лучше описывает последовательность 2, 5, 11, 23, 47,...

Правильный способ решить это - решить уравнения рекуррентности.

Ответ 5

Я думаю, что это будет экспоненциально. Каждое приращение до n приводит к вычислению в два раза больше.

Нет, это не так. Совсем наоборот:

Считаем, что для n итераций получаем время пробега R. Тогда для n + 1 итераций мы получим ровно R + 1.

Таким образом, темп роста является постоянным, а общая продолжительность выполнения действительно равна O (n).

Однако, я думаю, что предположение Димы о вопросе верно, хотя его решение слишком сложно:

Что вам нужно сделать, так это придумать решение закрытой формы, т.е. е. нерекурсивную формулу для T (n), а затем определить, что такое big-O этого выражения.

Достаточно исследовать относительный размер T (n) и T (n + 1) итераций и определить относительную скорость роста. Сумма, очевидно, удваивается, что непосредственно дает асимптотический рост.

Ответ 6

Во-первых, все четыре ответа хуже, чем 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 ^ п. Теперь сделайте остальную часть своей домашней работы... и изучите O (n * log n)

Ответ 7

Вычисление решения замкнутой формы рекурсии легко. При проверке вы предполагаете, что решение

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, очевидно, есть Theta (2 ^ n), поэтому правильный ответ является третьим.

Людям, которые отвечали O (n): Я больше не мог согласиться с Димой. Проблема состоит в том, что не запрашивает самую строгую верхнюю границу вычислительной сложности алгоритма для вычисления T (n) (который теперь будет O (1), так как его замкнутая форма была предоставлена). Задача требует самой жесткой верхней оценки на T (n), и это экспоненциальная.