Java Math.pow（a，b）时间复杂度

time-complexity java

2022-09-04 20:21:07

我想问一下以下代码的时间复杂度。是O（n）吗？（Math.pow（） O（1）的时间复杂度是 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]);

   }
}

答案 1

@Blindy讨论了Java在实现时可以采取的可能方法。pow

首先，一般情况下不能重复乘法。它不适用于指数不是整数的一般情况。（的签名是！powMath.pow(double, double)

在 OpenJDK 8 代码库中，的本机代码实现可以通过两种方式工作：pow

中的第一个实现使用幂级数。C 注释中对该方法的描述如下：e_pow.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)

中的第二个实现是标准 C 库提供的函数的包装器。包装器处理边缘情况。w_pow.cpow

现在，标准 C 库可能使用特定于 CPU 的数学指令。如果是这样，并且JDK构建（或运行时）选择了¹作为第二个实现，那么Java也会使用这些指令。

但无论哪种方式，我都看不到任何使用重复乘法的特殊情况代码的痕迹。您可以放心地假设它是 .O(1)

^{1 - 我还没有深入研究如何进行选择。}

答案 2

你可以认为是 O（1）。Math.pow

有一些可能的实现，从CPU汇编程序指令（Java不使用它）到基于（例如）泰勒级数扩展的几个术语的稳定软件实现（虽然不完全是泰勒实现，但有一些更具体的算法）。

如果这是你所担心的，它绝对不会重复倍增。

Java Math.pow（a，b） 时间复杂度

Java Math.pow（a，b）时间复杂度