求幂算法的复杂性
鉴于double x和肯定int y我需要找到x^y假设输入不会导致溢出。
我想出了一个算法，它使用以下事实x^y：
-
x^y=(x^floor(y/2))^2如果 y 是偶数。 -
x^y=x*(x^floor(y/2))^2如果 y 是奇数。 -
x^y=1如果 y 是 0
实施：
public static double power(double x, int y) {
if(y==0)
return 1;
double z=power(x, y>>>1);
z*=z;
if((y&1)==1)
z*=x;
return z;
}
我对它的复杂性分析有些挣扎。有log_2(y)递归级别，没有分支。在算法的每一层上z，乘法复杂度是O(n^2)中n的位数z。我们假设不会发生溢出，因此n最多是double类型中的一半。我是否将此乘法工作视为常数，这使算法的复杂度为O(log_2(y))？
回答
是的，该算法实际上称为二进制取幂，它的复杂性log_2(y)正如您所提到的。通常会考虑两个数字的乘法，O(1)除非数字可以是任意大的（也称为 BigInt）。这是因为一个数的位数总是恒定的。
笔记
另外，虽然与问题不完全相关，但我看到您提到乘法复杂度是O(n)n 位的数量。这不是真的。数字相乘的正常方法实际上是O(n^2). 但事实上，我们可以通过一些快速乘法算法做得更好。但这超出了这个问题的范围。