c++ - 通过平方时间复杂度求幂

Question

我不明白通过平方求幂如何导致 O(log n) 乘法。

在我看来，你最终做的不仅仅是 log n 乘法（其中 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;
}