请问以下代码的时间复杂度。是 O(n) 吗? (Math.pow() 的时间复杂度是O(1)?) 一般来说,Math.pow(a,b) 的时间复杂度是O(b) 还是O(1)?提前致谢。
public void foo(int[] ar) {
int n = ar.length;
int sum = 0;
for(int i = 0; i < n; ++i) {
sum += Math.pow(10,ar[i]);
}
}
最佳答案
@Blindy 讨论了 Java 在实现 pow
时可能采用的可能方法。
首先,一般情况不能重复乘法。它不适用于指数不是整数的一般情况。 (pow
的签名是 Math.pow(double, double)
!)
在 OpenJDK 8 代码库中,pow
的原生代码实现可以通过两种方式工作:
e_pow.c
中的第一个实现使用幂级数。该方法在 C 注释中描述如下:* Method: Let x = 2 * (1+f) * 1. Compute and return log2(x) in two pieces: * log2(x) = w1 + w2, * where w1 has 53-24 = 29 bit trailing zeros. * 2. Perform y*log2(x) = n+y' by simulating multi-precision * arithmetic, where |y'|<=0.5. * 3. Return x**y = 2**n*exp(y'*log2)
w_pow.c
中的第二个实现是标准 C 库提供的pow
函数的包装器。包装器处理边缘情况。
现在标准 C 库可以使用 CPU 特定的数学指令。如果是这样,并且 JDK 构建(或运行时)选择了1 第二个实现,那么 Java 也会使用这些指令。
但无论哪种方式,我都看不到任何使用重复乘法的特殊情况代码的踪迹。您可以安全地假设它是 O(1)
。
1 - 我还没有深入研究如何做出选择。
关于Java Math.pow(a,b) 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32418731/