Я понимаю, что он похож на последовательность Фибоначчи, которая имеет экспоненциальное время работы. Однако это рецидивное отношение имеет больше ветвей. Каковы асимптотические границы T(n) = 2T(n-1) + 3T(n-2)+ 1?Каково время запуска: T (n) = 2T (n-1) + 3T (n-2) + 1
Обычно вам нужно сделать некоторые предположения относительно 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).
Это фактически не отвечает на вопрос. – 2013-02-20 23:49:31
Почему он не решает вопрос? Я даю вам функцию, которая удовлетворяет рекуррентному отношению и доказана как таковая. –
Потому что вопрос НЕОБХОДИМО сделать с аналитическим решением. – 2013-02-21 03:24:58
Этот тип рецидивов называется: non-homogeneous recurrence relations, и вам необходимо решить вначале однородное повторение (одно без константы в конце). Если вам интересно, прочитайте математику за ней.
Я покажу вам простой способ. Просто введите уравнение в wolfram-alpha и вы получите:
,
, который явно экспоненциальная сложность: O(3^n)
'T (n) = ... который явно является экспоненциальной сложностью: O (3^n)' 'O (3^n)' в ваших ответах и @ AndrewMao является асимптотическим 'T (n)' * поведение * значений.Это * не * алгоритмическая сложность вычисления «T (n)» (обратите внимание, что исходный вопрос помечен как «алгоритм» и «сложность времени»). Сложность времени выполнения итерации, как написано, действительно экспоненциальна, но вычисление «T (n)» из явной формулы имеет практическую сложность по времени «O (log n)» ([Сложность времени power()] (http: //stackoverflow.com/questions/5231096/time-complexity-of-power)). – dxiv
Если вы знаете, начальные условия, вы можете написать его от руки. T (0) =? T (1) =?. Из этого вы можете получить остальные термины – Jason
Число ветвей в t (n) = F (t (n-1), t (n-2)) одинаково для любого F, поэтому, если у вас есть решение для последовательности Фибоначчи, ... – Joni