通过对时间复杂度求平方来求幂

Question

我不明白平方取幂是如何产生O（log n）乘法的。

在我看来，你最终做的乘法似乎不止logn（其中n是指数的大小）。

示例：

              power(2,8)
       /                       
     pow(2,4)        *          pow(2,4)
    /                         /              
pow(2,2) * pow(2,2)          pow(2,2) * pow(2,2)
   /                            /              
 p(2,1)*p(2,1) p(2,1)*p(2,1)  p(2,1)*p(2,1)    p(2,1)*p(2,1)

这是七次乘法运算，就像正幂运算一样。

以下是我尝试过的3种方法：

long pow(int base, int exp)
{
  if(exp == 1)
    return base;
  else
    return base * pow(base, exp-1);
}
long pow2(int base, int exp)
{
  if(exp == 1)
    return base;
  else if(exp == 0)
    return 1;
  else
    if(exp % 2 == 0)
      return pow2(base * base, exp/2);
    else
      return base * pow2(base * base, exp/2) ;
}
long pow3(int base, int exp)
{
    if(exp == 1)
        return base;
    int x = pow2(base,exp/2);
        if(exp%2 == 0)
            return x*x;
        else
            return base*x*x;
}

看起来，一旦递归达到底部，就会执行相同数量的乘法。。。

Answer 1

您应该只考虑一个分支，因为您保存结果而不重新计算分支。实际只进行以下乘法运算：

              power(2,8)
       /                       
     pow(2,4)        [*]        pow(2,4)
    /                         /              
pow(2,2) [*] pow(2,2)        pow(2,2) * pow(2,2)
   /                            /              
 p(2,1)[*]p(2,1) p(2,1)*p(2,1)  p(2,1)*p(2,1)    p(2,1)*p(2,1)

Answer 2

您显示的是一个二进制树，但递归函数不会调用自己两次，只调用一次，所以它只遍历一个logN路径。

此外，递归对于这个算法来说是愚蠢的（缓慢、复杂、脆弱）。只需在指数位上循环：

long pow(long base, int exp) {
    long result = 1;
    while (exp > 0) {
        if (exp & 1) result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

Answer 3

让我们看看您的示例2^8。在第一步中，你必须计算2^4。当你得到结果时，就把它自己相乘。你不必计算整棵树，因为你已经知道结果了。让我们看看你的示例树。在这种情况下，您只需要计算最左边的树。这意味着只有2^4，2^2，2^1，然后使用结果得到2^8。

你的功能应该是这样的：

int power(int base, int power) {
    if (power == 0)
        return 1;
    if (power == 1)
        return base;
    int result = power(base, power / 2);
    result *= result;
    if (power % 2 == 1)
         result *= base;
    return result;
}