證明斐波那契遞歸算法的時間複雜度

Question

我想通過歸納法在我的算法教科書中理解證明。下面是筆者使用誘導的T（n）的將永遠是證明大於2 ^（N/2）（這是計算使用遞歸算法的第n個斐波納契數）：

我不要什麼」不懂的是他操縱方程的最後一步。他怎麼去從：

> 2^(n-1)/2 + 2^(n-2)/2 +1 

到

> 2^(n-2)/2 + 2^(n-2)/2 +1 

他只是隨機地改變2^(n-1)/2到2^(n-2)/2。這是一個錯誤嗎？

謝謝。

Answer 1

我認爲，特定的步驟逃跑的假設是：

T(n-1) > T(n-2) 

因此，我們可以形成一個代數不等式：

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2) + 1 

我們可以從右邊砍掉了+ 1（因爲對於任何在LESSER方面減去的東西，不等式仍然適用）：

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2) 

由此看來，替代我們的T（M）= 2 ^（M/2）（對於小於n任何少和> 2，其中n-1和n-2都合格）：

2^(n-1)/2 + 2^(n-2)/2 + 1 > 2^(n-2)/2 + 2^(n-2)/2 

，讓你那個特定的步驟。正如我上面的海報所述，這是故意做到的，達到2 ^（n/2）。

Answer 2

這是故意的，如果你仔細觀察這是一個不公平的事情，他用它來完成誘導步驟。

注意錯字，應該說「我們必須證明T（n）> 2 ^（n/2）」而不是<。