Vorrei chiedere la complessità temporale del seguente codice. È O (n)? (La complessità temporale di Math.pow() O (1)?) In generale, Math.pow (a, b) ha complessità temporale O (b) o O (1)? Grazie in anticipo.Java Math.pow (a, b) complessità temporale
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 parla di possibili approcci che Java potrebbe adottare nell'implementazione di pow.
Prima di tutto, il caso generale non può essere ripetuto moltiplicando. Non funzionerà nel caso generale in cui l'esponente non è un numero intero. (! La firma per pow è Math.pow(double, double))
Nel OpenJDK 8 codebase, l'implementazione del codice nativo per pow può funzionare in due modi:
La prima implementazione in e_pow.c utilizza una serie di potenze. L'approccio è descritto nei commenti C come segue:
* 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)
la seconda implementazione in w_pow.c è un involucro per la funzione pow fornito dalla libreria standard C. Il wrapper si occupa di casi limite.
Ora è possibile che la libreria C standard utilizzi le istruzioni matematiche specifiche della CPU. In caso affermativo, e la build JDK (o runtime) ha selezionato la seconda implementazione, quindi Java avrebbe utilizzato anche queste istruzioni.
Ma in entrambi i casi, non vedo traccia di alcun codice di caso speciale che utilizza ripetute moltiplicazioni. Puoi tranquillamente supporre che sia O(1).
1 - non ho approfondito il modo in cui la selezione è/può essere fatto.
Non è mai necessario usare la moltiplicazione ripetuta. Esiste un algoritmo * O (log N) * per l'esponenziazione di interi. – EJP
@EJP - 1) Cosa è "necessario" e ciò che accade in realtà non è la stessa cosa. 2) Per 'int' e' long', puoi probabilmente sintonizzare l'algoritmo con casi speciali in modo che 'O (N)' sia più veloce di 'O (logN)' nell'intervallo di 'N' e' X' dove tu non ottenere overflow intero. –
@EJP E.g. considera X == 0, 1 e 2 e X <0 come casi speciali. Se gestisci il caso X == 2 usando i turni, log3 (2^32) è <21; cioè X> = 3 richiede 21 o meno cicli di moltiplicazione ripetuta. –
Si può considerare Math.pow di essere O (1).
Esistono alcune possibili implementazioni, che vanno da un'istruzione assemblatore di CPU (Java non lo utilizza) a un'implementazione software stabile basata su (ad esempio) l'espansione della serie Taylor su alcuni termini (sebbene non esattamente l'implementazione di Taylor , ci sono alcuni algoritmi più specifici).
Non si moltiplicherà ripetutamente se questo è ciò che ti preoccupa.
Perché Java non dovrebbe usare le istruzioni dell'assemblatore? L'implementazione è nativa. – chrylis
Nessuno lo fa, inclusa C. L'implementazione hardware non è completamente conforme agli standard (rispetto alla gestione IIRC di NaN). Devi forzare esplicitamente il compilatore C a utilizzare le istruzioni hardware ('-ffastmath' per gcc per esempio). – Blindy
@chrylis Nessuna architettura informatica che conosco ha un'istruzione per il calcolo dei poteri. L'implementazione più semplice sarebbe 'exp (b * log (a))' –
se si desidera solo potenze di interi, scrivere la propria funzione di potenza è meglio. Dato che ci sono solo poche potenze di 10 che si adattano a un int, usa semplicemente una tabella di ricerca e stai bene con O (1) –
@ LưuVĩnhPhúc, ma facendo iterativamente significa che fai b operazioni per a^b. non è vero? Nella domanda originale, se la lunghezza dell'array è n, l'intervallo dell'array è compreso tra 0 e n e il valore massimo è almeno n-1. Quindi il codice sopra avrà la complessità O (n^2) no? –
Dove ho detto che fai in modo iterativo i poteri? Quello che ho detto è una [tabella di ricerca] (https://en.wikipedia.org/wiki/Lookup_table) come 'int pow10 [] = {1, 10, 100, 1000, ... 1000000000};' e per ottenere 'Math.pow (10, i)' usa semplicemente 'pow10 [i]'. Anche se moltiplichi manualmente, hai solo bisogno di O (log n) con [esponenziazione per quadratura] (https: //en.wikipedia.org/wiki/Exponentiation_by_squaring) ([Il modo più efficace per implementare una funzione di potenza basata su interi pow (int, int)] (http://stackoverflow.com/q/101439/995714), non come O (n) come fare it itativamente –