我不明白平方求幂如何导致 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;
}
看起来，一旦递归触底，就会执行相同数量的乘法...
最佳答案
您应该只考虑一个分支，因为您保存了结果并且不重新计算分支。实际上只完成了以下乘法:
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)
关于c++ - 通过平方时间复杂度求幂，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18250132/