证明斐波那契递归算法时间复杂度
我试图理解我的算法教科书中的归纳证明。作者用归纳法证明了 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。这是一个错误吗？
谢谢。
I am trying to understand a proof by induction in my algorithms text book. Here's the author is proving using induction that the T(n) will always be greater than 2^(n/2) (This is for calculating the nth fibonacci number using the recursive algorithm):
What I don't understand is the very last step, where he is manipulating the equation. How does he go from:
> 2^(n-1)/2 + 2^(n-2)/2 +1
to
> 2^(n-2)/2 + 2^(n-2)/2 +1
He just randomly changes 2^(n-1)/2 to 2^(n-2)/2. Is this a mistake?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是故意的，如果你仔细观察，这是一个不等式，他用它来完成归纳步骤。
注意拼写错误，它应该说“我们必须证明 T(n) > 2^(n/2)”而不是 <。
It's deliberate, if you look closely it's an inequation and he uses it do finish the induction step.
Note the typo, it should say "We must show that T(n) > 2^(n/2)" and not <.
我相信这个特定的步骤违背了这样的假设：
因此，我们可以形成一个代数不等式：
可以从右侧去掉+1（因为对于在较小的一侧减去的任何东西，不等式仍然成立）：
我们 将此替换为 T(m) = 2^(m/2)（对于任何小于 n 且 > 2 的值，其中 n-1 和 n-2 都符合条件）：
这将帮助您完成特定的步骤。正如我上面的海报所说，这是故意这样做的，以达到 2^(n/2) 。
I believe that particular step runs off the assumption that:
Therefore, we can form an algebraic inequality:
We can lop off the + 1 from the right side (because the inequality will still hold true for anything subtracted away on the LESSER side):
From this, substitute our T(m) = 2^(m/2) (for anything less than n and > 2, which n-1 and n-2 both qualify):
That gets you that particular step. It's done this way deliberately as the poster above me stated, to get to 2^(n/2).