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

Я хотел бы задать временную сложность следующего кода. Это O (n)? (Является ли временной сложностью Math.pow() O (1)?) В общем случае Math.pow (a, b) имеет временную сложность O (b) или O (1)? Заранее спасибо.Java Math.pow (a, b) временная сложность

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]); 

    } 
}

источник

2015-09-05 seriously divergent

Если вам нужны только целые полномочия, лучше написать собственную функцию питания. Поскольку существует только несколько степеней 10, которые вписываются в int, просто используйте таблицу поиска, и вы хорошо относитесь к O (1) –

@ LưuVĩnhPhúc, но итеративно означает, что вы выполняете операции b для a^b. не так ли ?. В исходном вопросе, если длина массива равна n, диапазон массива находится между 0 и n, а max - не менее n-1. Таким образом, выше код будет иметь сложность O (n^2), не так ли? –

Где я сказал, что вы делаете итеративно за власть? То, что я сказал, это [таблица поиска] (https://en.wikipedia.org/wiki/Lookup_table), например 'int pow10 [] = {1, 10, 100, 1000, ... 1000000000};' и получить 'Math.pow (10, i)' просто используйте 'pow10 [i]'. Даже если вы размножаетесь вручную, вам нужно только O (log n) с [возведение в степень по квадрату] (https: //en.wikipedia.org/wiki/Exponentiation_by_squaring) ([Самый эффективный способ реализации целочисленной силовой функции pow (int, int)] (http://stackoverflow.com/q/101439/995714)), а не O (n), как делать он итеративно –

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

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

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

^{1 - я не вникал в то, как, когда выбор/может быть сделано.}

источник

2015-09-06 01:20:08

Никогда не нужно использовать повторное умножение. Существует алгоритм * O (log N) * для целочисленного возведения в степень. – EJP

@EJP - 1) Что является «необходимым», а то, что на самом деле происходит, - это не одно и то же. 2) Для 'int' и' long' вы можете настроить алгоритм на специальные случаи, чтобы 'O (N)' быстрее, чем 'O (logN)' в диапазоне 'N' и' X', где вы не получают целочисленного переполнения. –

@ EJP. обрабатывать X == 0, 1 и 2 и X <0 в качестве особых случаев. Если вы имеете дело с случаем X == 2 с использованием сдвигов, log3 (2^32) составляет <21; то есть X> = 3 требует 21 или менее раундов повторного умножения. –

Вы можете рассмотреть Math.pow как O (1).

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

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

источник

2015-09-06 00:04:44 Blindy

Почему Java не использует инструкцию ассемблера? Реализация является родной. – chrylis

Никто не делает, в том числе C. Реализация аппаратного обеспечения не полностью соответствует стандартам (в отношении обработки данных с помощью NaN IIRC). Вы должны явно заставить компилятор C использовать аппаратные инструкции (например, -ffastmath для gcc). – Blindy

@chrylis Нет компьютерной архитектуры, которую я знаю, имеет инструкцию для вычисления полномочий. Простейшей реализацией будет 'exp (b * log (a))' –

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

ответ

Смежные вопросы