Come sapere quando Big O è logaritmica?

Question

La mia domanda nasce dal post "Plain English Spiegazione di Big O" . Non conosco il significato esatto per la complessità logaritmica. So che posso fare una regressione tra il tempo e il numero di operazioni e calcolare il valore di X-squared, e determinare così la complessità. Tuttavia, vorrei sapere un metodo per determinare rapidamente su carta.

Come si fa a determinare la complessità logaritmica? Ci sono alcuni buoni punti di riferimento?

Answer 1

Non sono sicuro se questo è quello che vuoi dire, ma ... la complessità logaritmica di solito si pone quando si lavora con una struttura di dati spread-out come un albero binario bilanciato, che contiene 1 nodo alla radice, 2 bambini, 4 nipoti, 8 pronipoti, ecc in sostanza ad ogni livello il numero di nodi ottiene moltiplicati per un fattore (2), ma ancora solo uno di questi è coinvolto nella iterazione. O come un altro esempio, un ciclo in cui l'indice raddoppia ad ogni passo:

for (int i = 1; i < N; i *= 2) { ... }

Cose del genere sono le firme di complessità logaritmica.

Answer 2

Non rigorosa, ma si ha un algoritmo che è essenzialmente dividendo il lavoro necessario per essere svolto da metà su ogni iterazione, allora si ha complessità logaritmica. L'esempio classico è la ricerca binaria.

Answer 3

teorema di solito funziona.

Answer 4

Se si vuole solo sapere logaritmica Big Oh, essere alla ricerca di quando i dati viene tagliato a metà ogni fase della ricorrenza.

Questo perché se si stanno elaborando i dati che è 1/2 grande come il passaggio prima di esso, è una serie infinita.

Answer 5

Ecco un altro modo di dirlo.

Supponiamo che il vostro algoritmo è lineare nel numero di cifre nella dimensione del problema. Così, forse, si dispone di un nuovo algoritmo per fattorizzare un gran numero, che si può mostrare di essere lineare nel numero di cifre. Un numero di 20 cifre prende in tal modo il doppio del tempo di fattore come un numero a 10 cifre utilizzando il vostro algoritmo. Questo avrebbe registro complessità. (E sarebbe qualcosa di valore per l'inventore.)

Bisezione ha lo stesso comportamento. Ci vogliono circa 10 passi bisezione per tagliare la lunghezza dell'intervallo di un fattore di 1024 = 2 ^ 10, ma solo 20 passi taglierà l'intervallo di un fattore 2 ^ 20.

Log complessità non significa sempre un algoritmo è veloce su tutti i problemi. Il fattore lineare di fronte alla O (log (n)) può essere grande. Così il vostro algoritmo può essere terribile su piccoli problemi, non sempre utili fino a quando la dimensione del problema è sensibilmente grande che altri algoritmi muoiono di una morte esponenziale (o polinomiale).