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

Question

我想问一下下面代码的时间复杂度。是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]);

   }
}

Answer 1

@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.
  • 1. Perform y*log2(x) = n+y’ by simulating multi-precision
  • arithmetic, where |y’|<=0.5.
  • 1. Return xy = 2nexp(y’log2)

• 中的第二个实现w_pow.c是pow对标准C库提供的功能的包装。包装器处理边缘情况。

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

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

1-我尚未研究如何/何时进行选择。