Каталонские числа, сложность рекурсивной функции

Question

Следующая функция производит n-е число в catalan numbers. Какова точная функция временной сложности этой функции или как ее найти?

int catalan(int n) 
{ 
    if (n==0 || n==1) 
     return 1; 

    int sum = 0; 
    for(int i=1;i<n;i++) 
     sum += catalan(i)*catalan(n-i); 
    return sum; 
} 

Примечание: Я знаю, что это самый худший способ вычислить каталонское число.

Answer 1

Чтобы оценить сложность, давайте сосредоточимся на число рекурсивных вызовов, выполняемых, пусть C(n).

Вызов для n подразумевает точно 2(n-1) рекурсивных звонков, каждый из которых добавляет свои собственные расходы, 2(C(1)+C(2)+...C(n-1)).

За звонок для n+1 подразумевается точно 2n рекурсивных звонков, каждый из которых добавляет собственные расходы, 2(C(1)+C(2)+...C(n-1)+C(n)).

По разнице C(n+1)-C(n) = 2+2C(n), которая может быть написана C(n) = 2+3C(n-1).

C(1) = 0 
C(2) = 2+2C(1) = 2+3C(0) = 2 
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8 
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26 
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80 
... 
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1) 

Для того, чтобы решить эти рецидивы легко заметить, что

C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1) 

Следовательно, для n>1 точной формулы

C(n) = 3^(n-1)-1 

Количество вызовов к Catalan(1) (постоянное времени), также C(n), а числа добавлений или умножений - C(n)/2 каждый.

Легко уменьшить сложность от O(3^n) к O(2^n), отметив, что все члены в петле (кроме среднего) вычисляются дважды - но это еще не делает его приемлемым реализацию :)

Answer 2

Предположим

1. любой шаг иначе, чем для-петли к;
2. суммирования и множественный в обмен на петле с и
3. Каталонский (г) Т (г)

В для цикла каталонского (п), каталонский (I) выполняет N-1 когда значение i от 1 до n-1 и каталан (ni) выполняет n-1 раз, где значение ni от n-1 до 1. Короче говоря, каталанский (i) и каталанский (ni) равны в два раза всем каталантическим (x), где значение x от 1 до n-1.

T(n) = 2(T(1) + T(2) + T(3) + ... + T(n-2) + T(n-1)) + k + (n-1)c 
Similarly, 
T(n-1) = 2(T(1) + T(2) + T(3) + ... + T(n-2)) + k + (n-2)c 

Reorder T(n) as 2(T(1) + T(2) + T(3) + ... + T(n-2)) + 2T(n-1) + k + (n-2)c + c 
T(n) = 2(T(1) + T(2) + T(3) + ... + T(n-2)) + k + (n-2)c + 2T(n-1) + c 
T(n) = T(n-1) + 2T(n-1) + c 
T(n) = 3T(n-1) + c 
T(n) = (3^2)T(n-2) + 3c + c 
T(n) = (3^3)T(n-3) + (3^2)c + 3c + c 
and so on... 
T(n) = (3^(n-1))T(n-(n-1)) + c(3^0 + 3^1 + 3^2 + ... + 3^(n-2)) 
T(n) = (3^(n-1))T(1) + ((3^(n-1)-1)/2)c 

Таким образом, время сложность O(3^N)