Я понимаю, что это похоже на последовательность Фибоначчи, которая имеет экспоненциальное время выполнения. Однако это рекуррентное соотношение имеет больше ветвей. Каковы асимптотические границы T(n) = 2T(n-1) + 3T(n-2)+ 1?
Каково время выполнения: T(n) = 2T(n-1) + 3T(n-2)+ 1
comment
Если вы знаете начальные условия, вы можете написать это от руки. Т(0) = ? Т(1)=?. Отсюда вы можете получить остальные термины
- person Jason schedule 21.02.2013
comment
Количество ветвей в t(n) = F(t(n-1),t(n-2)) одинаково для любого F, поэтому, если у вас есть решение для последовательности Фибоначчи,...
- person Joni schedule 21.02.2013
Ответы (2)
Обычно вам нужно будет сделать некоторые предположения относительно T(0) и T(1), потому что их будет экспоненциально много, и их значения могут определять функциональную форму T(n). Однако в данном случае это, похоже, не имеет значения.
Тогда рекуррентные соотношения этой формы могут быть решены путем нахождения их характеристических многочленов. Я нашел эту статью: http://www.wikihow.com/Solve-Recurrence-Relations
Я получил характеристический многочлен с корнями 3 и 1, так что угадываю форму T(n) = c_1*3^n + c_2. В частности, T(n) = 1/2*3^n - 1/4 удовлетворяет рекуррентному соотношению, и мы можем это проверить.
1/2*3^n - 1/4 = 2*T(n-1) + 3*T(n-2) + 1
= 2*(1/2*3^(n-1) - 1/4) + 3*(1/2*3^(n-2) - 1/4) + 1
= 3^(n-1) - 1/2 + 1/2*3^(n-1) - 3/4 + 1
= 3/2*3^(n-1) - 1/4
= 1/2*3^n - 1/4
Следовательно, это даст T(n) = Theta(3^n). Однако это может быть не единственная функция, которая удовлетворяет повторению, и другие возможности также будут зависеть от того, какие вы определили значения T(0) и T(1), но все они должны быть O(3^n).
person
Andrew Mao
schedule
20.02.2013
На самом деле это не отвечает на вопрос.
- person ; 21.02.2013
Почему не решает вопрос? Я даю вам функцию, которая удовлетворяет рекуррентному соотношению и доказана как таковая.
- person Andrew Mao; 21.02.2013
Потому что вопрос не имел АБСОЛЮТНО НИЧЕГО общего с аналитическим решением.
- person ; 21.02.2013
Вы действительно проявляете неуважение. Я не думаю, что вы вообще поняли вопрос, и теперь вы троллите двух человек, которые пытались на него ответить.
T(n) — это время работы алгоритма на конкретном входе размером n, а рекуррентное отношение определяет его структуру с рекурсией. Мы пытаемся найти T(n), используя это рекуррентное соотношение. Как вы думаете, о чем вопрос? Возможно, тебе стоит ответить на него, если ты считаешь себя таким крутым.
- person Andrew Mao; 21.02.2013
Рекурсивное отношение типа Фибоначчи (при рекурсивном применении) будет иметь экспоненциально много рекурсивных вызовов. Это комментарий об экспоненциальном времени выполнения. Ваш ответ не затрагивает аспект ветвления.
- person ; 21.02.2013
O(3^n) экспоненциально по n. Более того, линейная рекуррентность, о которой говорят люди, относится к решаемому многочлену, а не к самому уравнению. Нахождение коэффициента ветвления для линейного рекуррентного соотношения редко требует подсчета ветвей вручную. Фактически, именно так вы также можете получить золотое сечение из повторения Фибоначчи: en.wikipedia. org/wiki/, что элегантно было бы фактором ветвления — O(phi^n), если бы вы запускали алгоритм с таким же повторением.
- person Andrew Mao; 21.02.2013
Этот тип рекуррентных отношений называется: неоднородные рекуррентные отношения. решить вначале однородную рекуррентность (тот, что без константы в конце). Если вам интересно, прочитайте математику, стоящую за этим.
Я покажу вам простой способ. Просто введите свое уравнение в wolfram-alpha и вы получите:
,
что явно является экспоненциальной сложностью: O(3^n)
person
Salvador Dali
schedule
16.12.2015
T(n) = ... which is clearly an exponential complexity: O(3^n) O(3^n) как в вашем ответе, так и в ответе @AndrewMao является асимптотическим T(n) поведением значений. Это не алгоритмическая сложность вычисления T(n) (обратите внимание, что исходный вопрос помечен как algorithm и time-complexity). Временная сложность выполнения итерации, как написано, действительно экспоненциальна, но вычисление T(n) по явной формуле имеет практическую временную сложность O(log n) (Временная сложность мощности()).
- person dxiv; 20.12.2015
