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

Question

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

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

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;
}

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

1

algorithm c++catalan time-complexity

Решение

Другие решения

Предполагать

любой шаг, кроме цикла for, равен k;
суммирование и кратно в цикле для C и
каталанский (т) является Т (т)

В цикле for каталонского (n) каталанский (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)

2

Источник

Accepted Answer

Чтобы оценить сложность, давайте сосредоточимся на количестве выполненных рекурсивных вызовов, 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) отметив, что все члены цикла (кроме среднего) вычисляются дважды, но это все равно не делает его приемлемой реализацией 🙂

4