Как найти временную сложность рекурсивного алгоритма?

Question

Как найти сложность следующего алгоритма:

int f(int n) 
{ 
    if(n<=1) { return 1; } 
    return f(n-1) + f(n-1); 
} 

это правильно уравнение рекурсии T(n) = 2*T(N-1) + c? Как его решить?

Answer 1

Я думаю, что ваше уравнение рекурсии верное.

Но этот конкретный случай достаточно прост, чтобы «просто подумать» об этом немного, не вдаваясь в «как решить рекурсии вообще».

---

Давайте посмотрим на е (3)

  f(3)   

    f(2) + f(2)   

f(1) + f(1) + f(1) + f(1) 

Итак, сколько звонков мы имеем? 1 + 2 + 4

Хмм .. как насчет f (4)?

      f(4) 

      f(3)   +   f(3) 

    f(2) + f(2)  +  f(2)  + f(2) 

f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1) 

Итак, сколько звонков у нас есть? 1 + 2 + 4 + 8

Таким образом, мы можем сделать обоснованное предположение для n = 5: 1 + 2 + 4 + 8 + 16. И если вы думаете об этом, это также имеет смысл, потому что: numCalls (f (5)) = 2 * numCalls (f (4)) + 1 (+ 1 происходит от вызова до самого f (5)).

Мы можем обобщить это

T(n) = sum(2^i) for i in (0, n-1) 

Теперь, если мы используем тот факт, что

sum(2^i) for i in (0, n-1) == 2^n - 1 

это становится совершенно очевидно, что

T(n) = 2^n - 1 

, который находится в O(2^n)

---

в качестве упражнения:

Докажите по индукции, что

T(n) = 2*T(n-1) + 1 <=> T(n) = 2^n - 1 

Или немного больше общего:

T(n) = 2*T(n-1) + c <=> T(n) = c*(2^n - 1) 

---

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