Java Math.pow（a，b）时间复杂度 [英] Java Math.pow(a,b) time complexity

问题描述

我想问下面代码的时间复杂度。是O（n）？ （Math.pow（）的时间复杂度是否为O（1）？）一般来说，Math.pow（a，b）是否具有时间复杂度O（b）或O（1）？在此先感谢。

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.

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 时采取这些方法。

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

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

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)!)

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

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

• e_pow.c 中的第一个实现使用幂级数。该方法在C评论中描述如下：

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

* 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 中的第二个实现是由 pow 函数提供的包装器。标准C库。包装器处理边缘情况。

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.

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

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.

但要么方式，我看不到任何使用重复乘法的特殊情况代码的痕迹。您可以放心地假设它是 O（1）。

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).

^{1 - 我没有深入研究何时/可以进行选择。}

这篇关于Java Math.pow（a，b）时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！