Java Math.pow(a, b) временная сложность

Я хотел бы задать временную сложность следующего кода. Это 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]);

   }
}

Ответы

Ответ 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, предоставляемой библиотекой Standard C. Обертка имеет дело с краевыми случаями.

Теперь возможно, что библиотека Standard C использует специфичные для процессора математические инструкции. Если бы это было так, и JDK построил (или выполнил время) выбранную 1 вторую реализацию, тогда Java тоже будет использовать эти инструкции.

Но в любом случае я не вижу никаких следов какого-либо специального кода кода, который использует повторное умножение. Вы можете смело предположить, что это O(1).

1 - Я не размышлял о том, как сделать выбор/.

Ответ 2

Вы можете считать Math.pow равным O (1).

Есть несколько возможных реализаций, начиная от инструкции ассемблера процессора (Java не использует это) до стабильной реализации программного обеспечения, основанной на (например) расширении серии Taylor на нескольких терминах (хотя это не совсем реализация Taylor, есть еще несколько конкретных алгоритмов).

Это определенно не будет многократно размножаться, если это то, о чем вы беспокоитесь.