用两个递归情况确定递归方法的大O？
用两个递归情况确定递归方法的大O？
提问于 2016-02-24 06:37:34
我目前正在为一个递归指数函数计算Big，这个函数在n%2 == 0时会走捷径。守则如下：
public static int fasterExponent(int x, int n){
if ( n == 0 ) return 1;
if ( n%2 == 0 ){
int temp = fasterExponent(x, n/2);
return temp * temp;
}
return x * fasterExponent(x, --n); //3
}我知道，如果没有(n%2 == 0)情况，这个递归指数函数将是O(n)。包含(n%2 == 0)的情况加快了执行时间，但我不知道如何确定其复杂性和见证c的值。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-02-24 06:52:06
答案是O(log ).
原因： fasterExponent(x, n/2)在每个步骤中将输入减半，当它到达0时，我们就完成了。这显然需要日志n步。但是fasterExponent(x, --n);呢？当输入是奇数时，我们这样做，在下一步，它将是偶数，我们回到n/2的情况。让我们考虑最坏的情况，每次我们除以n的时候，我们都要这样做。那么，我们每次做第一个递归步骤的时候，都要做第二个递归步骤。所以我们需要2* log操作。这仍然是O(log n)。希望我的解释能帮上忙。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35594983
复制相关文章
相似问题
腾讯云开发者
