理论上是对数复杂度，但实际上是线性的

Question

看一下下面的代码来找到 X^y。

/* Find exponent in logarithmic complexity */
int findPower(int base, exponent){
     if( 1 == exponent ) return base;
     return (findPower(base, exponent/2)*findPower(base, exponent-exponent/2));
}

int main(int argc, char *argv[]){
    if(argc < 3) {
        printf("Usage :: logpow baseNumber power\n");
        return -1;
    }
    printf("%s ^ %s  =  %d\n", argv[1], argv[2], findPow( atoi(argv[1]),
                                                          atoi(argv[2])) );
    return 0;
}

分析表明，其复杂度为 theta(log(n))。 但我运行它来测量时间，这是结果

Run 1: (calculating 1^500_million)
user-lm Programming # time ./a.out 1 500000000
1 ^ 500000000  =  1

real    0m5.009s
user    0m5.000s
sys 0m0.000s


Run 2: (calculating 1^1_Billion)
user-lm Programming # time ./a.out 1 1000000000
1 ^ 1000000000  =  1

real    0m9.667s
user    0m9.640s
sys 0m0.000s


Run 3: (calculating 1^2_Billion)
user-lm Programming # time ./a.out 1 2000000000
1 ^ 2000000000  =  1

real    0m18.649s
user    0m18.630s
sys 0m0.000s

从上面我们可以看到，实际的时间复杂度具有线性行为而不是对数！

复杂性如此巨大差异的原因可能是什么？

问候，

微内核

Answer 1

实际上，每次调用都会调用 2 个函数调用。递归树将是高度为 log(exponent) 的二叉树，因此其中的节点数将为 2^log(exponent) == exponent。所以总的来说它变成了一个线性算法。您可以这样重写它以获得更好的性能：

int findPower(int base, int exponent){
    if( 0 == exponent ) return 1;
    int temp = findPower(base, exponent/2);
    if(exponent % 2 == 0) return temp * temp;
    return temp * temp * base;
}

技巧是，您必须存储 findPower(base, exponent/2) 的值才能获得对数复杂度。递归树仍然具有 log(exponent) 高度，但每个节点现在只有一个子节点，因此会有 log(exponent) 节点。如果您实际上调用它两次，其降低性能的程度甚至会超过线性性能。如果您已经拥有相同的值，则无需第二次计算相同的值！

正如 @David Schwartz 指出的，如果指数加倍，代码中的调用次数将加倍。但是，当您保存值时，将指数加倍只会再调用一次。

Answer 2

你的分析不正确，是O(N)。

当你把N从10亿增加到20亿时，你必须对10亿进行两次幂运算。因此，N 加倍会使需要完成的工作加倍。那是 O(N)。

Answer 3

算法复杂度有一个正式的表示：

T(n) = 2T(n/2) + c

其中n 是指数。得出

T(n) = Theta(n)

分析不正确。