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.
  *      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库提供的函数的包装器.包装器处理边缘情况.

现在,标准C库可能使用CPU特定的数学指令.如果它这样做,和JDK版本(或运行时)选择¹第二种实现,那么Java将使用这些指令了.

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

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

Answer 2

你可以认为Math.pow是O(1).

有一些可能的实现,从CPU汇编程序指令(Java不使用它)到稳定的软件实现,基于(例如)泰勒系列扩展的几个术语(虽然不完全是泰勒实现,还有一些更多具体算法).

如果这是你担心的话,它绝对不会反复增加.