通过平方时间求幂 [英] exponentiation by squaring time complexity

问题描述

我不知道平方的乘幂是如何导致O（log n）乘法的。

I don't understand how the exponentiation by squaring results in O(log n) multiplications.

在我看来，您最终要做的不只是log n乘法（其中n是指数的大小）。

It seems to me that you end up doing more than log n multiplications (where n is the size of the exponent).

示例：

              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)

这是七个乘法，就像正则幂运算。

That's seven multiplications, just like regular exponentiation.

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

Here are 3 methods I've tried:

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;
}

似乎一旦递归触底，乘法的次数相同被执行...

It seems like, once the recursion bottoms out, the the same number of multiplications are performed...

推荐答案

您应该只考虑一个分支，因为这样可以保存结果并且不重新计算分支。实际上仅完成以下乘法：

You should only consider one branch, since you save the result and don't recompute branches. Only the following multiplications are actually done:

              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)

这篇关于通过平方时间求幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！