使用遞歸關係來證明函數具有指數運行時？

Question

下面是一個簡單的C程序：

int f(int n) { 
    if(n==0 || n==1) { 
    return n; 
    } else { 
    return 2 * f(n - 1) + 3 * f(n - 2); 
    } 
} 

這個程序有指數時間複雜度。您可以在此圖中的函數調用中看到了f(5)：

我要顯示出該函數具有指數使用遞推公式複雜而已，不是通過繪製圖和計算的功能數量調用。

我想出的遞推關係是

T（N）= T（N-1）+ T（N-2）+ C

展開式給出

T（N）= 2T（N - 2）+ T（N - 3）+ 2C

但是，不知如何解決THI進一步。我怎樣才能解決這種復發關係？

Answer 1

對於初學者來說，你的復發需要某種形式的基本情況，因爲否則，當你打0。爲了簡化它的不確定，讓我們說，

T（0）=一

T（1 ）= A + b

T（N + 2）= T（N）+ T（N + 1）+ C

讓我們開始向外擴展這個遞推的前幾個術語：

• T（0）=α
• T（1）= A + B
• T（2）= 2A + B + C
• T（3）= 3A + 2B + 2C
• T（4）= 5A + 3B + 4C
• T（5）= 8A + 5B + 7C
• T（6）= 13A + 8B + 12C
• T（7）= 21A + 13B + 20c

這裏有一個非常有趣的圖案。讓我們分別看a，b和c項的係數。的一個項的係數遵循模式

1，1，2，3，5，8，13，21，...

這斐波納契數列，由一個步驟偏移。 b項的係數是

0,1,1,2,3,5,8,13 ......

這就是正好是斐波那契數列。最後，讓我們來看看在C條款：

0，0，1，2，4，7，12，20，...

嗯，看起來不熟悉。但是，如果我們把它並排側的一個方面，我們看到這一點：

答：1，1，2，3，5，8，13，21，...

b：0,0,1,2,4,7,12,20，...

請注意，b項是所有a項減去！換句話說，斐波那契數列移動了一步，但是從每一項中減去1。

基於這些觀察，我們可以推測以下爲真：

T（N）=中國aF _{n + 1個} + BF _Ñ + C（F _{N + 1} - 1）

我們現在可以嘗試通過歸納證明這一點。作爲我們的基例：

T（0）=α= 1A + 0B + 0C = 1A + 0B +（1 - 1）C =中國aF + BF + C（F - 1）

T（1）= A + b = 1A + 1B + 0C = 1A + 1B +（1 - 1）C =中國aF + BF + C（F - 1）

對於我們的感應步驟中，讓我們假設，對於一些自然數n，即

T（N）=中國aF _{n + 1個} + BF _Ñ + C（F _{N + 1} - 1）

和

T（N + 1）=中國aF _{N + 2} + BF _{n + 1個} + C（F _{N + 2} - 1）

然後，我們有

T（N + 2）= T（N）+ T（N + 1）+ C

=中國aF _{n + 1個} + BF _ñ + C（F _{N + 1} - 1）+自動對焦 _{N + 2} + BF _{n + 1個} + C（F _{N + 2} - 1）+ C

=α（F _{N + 1} + F _{N + 2}）+ B（F _Ñ + F _{N + 1}）+ C（F _{n + 1個} + F _{N + 2} - 2 + 1）

=中國aF _{N + 3} + BF _{N + 2} + C（F _{N + 3} - 1）

這完成了歸納，所以我們的公式必須正確！

那麼這與效率有什麼關係呢？那麼，Binet's formula告訴我們，其中φ是golden ratio（約1.61）。這意味着，

T（N）=中國aF _{n + 1個} + BF _Ñ + C（F _{N + 1} - 1）=一個Θ（φ ^Ñ）+ B Θ（ φ ^ñ）+ C Θ（φ ^ñ）= Θ（（A + b + C）φ ^ñ）

所以只要a + b + c ≠ 0，運行時間是Θ（φ ⁿ），它是指數的。

希望這有助於！