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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

      1. Perform y*log2(x) = n+y’ by simulating multi-precision

    • arithmetic, where |y’|<=0.5.

      1. Return xnexp(y’log2)

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

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

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

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

以上是 Java Math.pow（a，b）时间复杂度 的全部内容， 来源链接： utcz.com/qa/431556.html

回到顶部