证明斐波那契递归算法的时间复杂度

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）”而不是<。