Java Math.pow(a,b)时间复杂度

I would like to ask time complexity of the following code. Is it O(n)? (Is time complexity of Math.pow() O(1)? ) In general, is Math.pow(a,b) has time complexity O(b) or O(1)? Thanks in advance.

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

   }
}

2 个解决方案

#1

@Blindy talks about possible approaches that Java could take in implementing pow.

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

First of all, the general case cannot be repeated multiplication. It won't work for the general case where the exponent is not an integer. (The signature for pow is Math.pow(double, double)!)

首先，一般情况不能重复相乘。在一般情况下，指数不是整数。(pow的签名是数学。战俘(双、双)!)

In the OpenJDK 8 codebase, the native code implementation for pow can work in two ways:

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

The first implementation in e_pow.c uses a power series. The approach is described in the C comments as follows:

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)

The second implementation in w_pow.c is a wrapper for the pow function provided by the Standard C library. The wrapper deals with edge cases.

w_pow中的第二个实现。c是标准c库提供的pow函数的包装器。包装器处理边界情况。

Now it is possible that the Standard C library uses CPU specific math instructions. If it did, and the JDK build (or runtime) selected¹ the second implementation, then Java would use those instructions too.

现在，标准C库可能使用CPU特定的数学指令。如果是这样，JDK构建(或运行时)selected1是第二个实现，那么Java也会使用这些指令。

But either way, I can see no trace of any special case code that uses repeated multiplication. You can safely assume that it is O(1).

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

^{1 - I haven't delved into how when the selection is / can be made.}

1 -我还没有深入研究选择是如何进行的。

#2

You can consider Math.pow to be O(1).

您可以考虑数学。战俘是O(1)。

There's a few possible implementations, ranging from a CPU assembler instruction (Java doesn't use this) to a stable software implementation based on (for example) the Taylor series expansion over a few terms (though not exactly the Taylor implementation, there's some more specific algorithms).

有一些可能的实现，从CPU汇编指令(Java不使用这个)到基于(例如)泰勒级数展开的稳定软件实现(例如，虽然不是泰勒实现，但有一些更具体的算法)。

It most definitely won't repeatedly multiply if that's what you're worried about.

如果这是你担心的，它肯定不会重复相乘。

#1