证明Fibonacci递归算法时间复杂度

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)> 2 ^(n/2)"而不是<.