Рекурсия и Большой О

Question

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

Укажите наилучшую скорость роста, используя обозначение big-Oh, для решения следующего случая?

T (1) = 2

T (n) = 2T (n - 1) + 1 для n> 1

И выбор:

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

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

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

Answer 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 ⁿ ).

Answer 2

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

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

Answer 3

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

Другими словами: повторение дает:

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

Какая система обозначений big-Oh лучше всего описывает последовательность 2, 5, 11, 23, 47, ...

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

Answer 4

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

Answer 5

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

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

Answer 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)

Answer 7

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

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

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

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

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

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

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