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

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指出的那样,如果exponent加倍,代码中调用的次数将增加一倍.但是当你保存这些值时,exponent只需要再加一次调用.