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

Question

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

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

Т(1) = 2

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

И выбор такой:

• О (п журнал п)
• О(п^2)
• О (2 ^ п)
• О(п^п)

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

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

Answer 1

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

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

Т(п) = 2Т(п-1) + 1
Т(п) = 4Т(п-2) + 2 + 1
Т(п) = 8Т(п-3) + 4 + 2 + 1
Т(п) = ...

Видите образец?

Т(п) = 2^n-1⋅Т(1) + 2^n-2 + 2^n-3 + ... + 1
Т(п) = 2^n-1⋅2 + 2^n-2 + 2^n-3 + ... + 1
Т(п) = 2^н + 2^n-2 + 2^n-3 + ... + 1

Следовательно, самая точная граница — это Θ(2^н).

Answer 2

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

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

Answer 3

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

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

  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

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

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

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

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

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

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

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

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

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

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