以下伪码的大O复杂度是多少？
以下伪码的大O复杂度是多少？
提问于 2013-11-27 09:27:17
以下伪码的计算复杂度是多少？
integer recursive (integer n) {
if (n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}在现实世界中，调用将得到优化并产生线性复杂性，但是在计算大o的内存模型下，复杂度是多少？2^n。
回答 1
Stack Overflow用户
发布于 2013-11-27 09:44:27
你的复杂性将是
为什么会这样呢？简单的数学归纳法证明：
- N=1:特例，计数步骤= 1。
- N=2，很明显
= 2，所以这是正确的
- 让它对
N=K是正确的，也就是说，对于N=K，它将是
- 假设是
N=K+1。recursive函数将递归地为N=K调用两次：recursive(K+1) = recursive(K) + recursive(K)，因为它遵循代码。这就是：
。所以，对于N=K+1我们有
步骤。
所以我们已经证明了N的复杂性
在一般情况下(从数学归纳的定义)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20238439
复制相关文章
相似问题
腾讯云开发者
