在第 2 章中提到求幂时，作者提到了
“所需的乘法次数显然最多为 2 log n(基数为 2)，因为在 大多数两个乘法(如果 n 是奇数)需要将问题减半。同样，可以编写和求解递推公式。”
代码如下:
int pow( int x, unsigned int n)
{
/*1*/ if( n == 0 )
/*2*/ return 1;
/*1*/ if( n == 1 )
/*4*/ return x;
/*5*/ if( even( n ) )
/*6*/ return( pow( x*x, n/2 ) );
else
/*7*/ return( pow( x*x, n/2 ) * x );
}
问: 正如作者所说，
2^16最多需要8次乘法
2^15 ... 7 ...
2^14 ... 7 ...
2^13 ... 7 ...
2^12 ... 7 ...
其实我是根据代码执行的:
2^16 .... 4 ...
2^15 .... 6 ...
2^14 ... 5 ...
2^13 ... 5 ...
2^12 ... 4 ...
那么，有什么地方不对吗？
最佳答案
没有矛盾或错误——书上给出了上限，而您正在查看乘法的确切数目。
确切的乘法次数(对于 n>0)是 floor(log_2(n)) + bitcount(n) - 1。这只是通过检查代码——偶数情况(执行一次乘法)对应于 0输入中的位，奇数情况(执行额外的乘法)对应输入中的 1 位，代码在到达最高位时停止。
书上说 2*log_2(n) 是乘法次数的上限。这与确切的公式一致:floor(log_2(n)) <= log_2(n) 和 bitcount(n) - 1 <= log_2(n)。所以 floor(log_2(n)) + bitcount(n) - 1 <= 2*log_2(n)。
从精确的公式可以看出，n的bitcount越低，上限越差。最坏的情况是当 n 是 2 的幂时:然后正好执行 log_2(n) 次乘法，并且上限偏离因子 2。最好的情况是当 n 小于 1 的幂时2:那么上限将仅偏离 1。这与您的经验结果表相匹配。
关于c - 数据结构中的求幂和 C 中的算法分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42995584/