Сложность рекурсии: T (n) = T (n-1) + T (n-2) + C

Question

Я хочу понять, как достичь сложности приведенного ниже отношения повторения.

T(n) = T(n-1) + T(n-2) + C Учитывая T(1) = C и T(2) = 2C;

В общем случае для уравнений типа T(n) = 2T(n/2) + C (при Т (1) = C), я использую следующий метод.

T(n) = 2T(n/2) + C 
=> T(n) = 4T(n/4) + 3C 
=> T(n) = 8T(n/8) + 7C 
=> ... 
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c 

Теперь, когда n/2^k = 1 => K = log (n) (к основанию 2)

T(n) = n T(1) + (n-1)C 
    = (2n -1) C 
    = O(n) 

Но, я не могу придумать подобный подход к проблеме у меня под вопросом. Пожалуйста, исправьте меня, если мой подход неверен.

Answer 1

Сложность связана с входным размером, где каждый вызов производят бинарное дерево вызовов

Где T(n) сделать 2n звонки в общей сложности ..

T(n) = T(n-1) + T(n-2) + C

T(n) = O(2n-1) + O(2n-2) + O(1)

O(2n)

Таким же образом, вы можете обобщить свой рекурсивную функцию, как Фибоначчи числа

T(n) = F(n) + (C * 2n)

Далее вы можете использовать прямой формула вместо рекурсивного способа

Используя сложный метод, известный как Binet's Formula

Answer 2

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

Answer 3

Является ли «хуже экспоненциального» достаточно точным для ваших целей? Специальный случай C = 0 определяет http://en.wikipedia.org/wiki/Fibonacci_number, который вы можете видеть из статьи экспоненциально. Предполагая, что C положителен, ваша серия будет расти быстрее, чем эта. Фактически, ваша серия будет лежать между рядами Фибоначчи и вариантом серии Фибоначчи, в котором золотое соотношение заменяется чем-то очень большим.

Answer 4

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

Мы знаем, что T(1) = c и T(2) = 2c и T(n) = T(n-1) + T(n-2) + c.

Так что просто напишите T(n) и начните расширяться ...

T(n) = T(n-1) + T(n-2) + c 
T(n) = 2*T(n-2) + T(n-m) + 2c 
T(n) = 3*T(n-3) + 2*T(n-4) + 4c 
T(n) = 5*T(n-4) + 3*T(n-5) + 7c 
etc ... 

Вы видите, что коэффициенты являются номерами Фибоначчи сами!

Звоните F(n)nth Номер Фибоначчи. F(n) = (phi^n + psi^n)/sqrt(5) где phi = (1+sqrt(5))/2 и psi = -1/phi, то мы имеем:

T(n) = F(n)*2c + F(n-1)*c + (F(n+1)-1)*c 

Вот некоторый быстрый код, чтобы продемонстрировать:

def fib_gen(n): 
    """generates fib numbers to avoid rounding errors""" 
    fibs=[1,1] 
    for i in xrange(n-2): 
     fibs.append(fibs[i]+fibs[i+1]) 
    return fibs 

F = fib_gen(50) #just an example. 
c=1 

def T(n): 
    """the recursive definiton""" 
    if n == 1: 
     return c 
    if n == 2: 
     return 2*c 
    return T(n-1) + T(n-2) + c 

def our_T(n): 
    n=n-2 #just because your intials were T(1) and T(2), sorry this is ugly! 
    """our found relation""" 
    return F[n]*2*c + F[n-1]*c + (F[n+1]-1)*c 

и

>>> T(24) 
121392 
>>> our_T(24) 
121392 

Answer 5

Этого типа рецидивов называется: non-homogeneous recurrence relations и вы должны решить вначале однородный рекуррент (тот, у которого нет константы в конце). Если вам интересно, прочитайте математику за ней.

Я покажу вам простой способ. Просто введите уравнение в wolfram-alpha и вы получите:

Так сложность растет так же, как либо Лукас или числа Фибоначчи (чем больше из них).

Но оба они имеют один и тот же темп роста:

и, следовательно, ваш темп роста является экспоненциальным золотым сечением: O(phi^n)