Logaritmica vs doppia complessità tempo logaritmico

Question

Nelle applicazioni del mondo reale c'è un beneficio concreto quando si usa $ \ mathcal {O} (\ log (\ log (n)) $ invece di $ \ mathcal {O} (\ log (n)) $ algoritmi?

Questo è il caso quando uno uso per esempio van Emde Boas alberi al posto dei più convenzionali binari implementazioni di ricerca albero. Ma per esempio, se prendiamo $ n <10 ^ 6 $ quindi nel migliore dei casi il doppio algoritmo logaritmica supera quella logaritmica per (circa) un fattore pari a $ 5 $. E anche, in generale, l'attuazione è più difficile e complessa.

Dato che io personalmente preferisco BST oltre VEB-alberi, che cosa ne pensi?

Si potrebbe facilmente dimostrare che:

$ \ qquad \ displaystyle \ forall n <10 ^ 6. \ \ Frac {\ log n} {\ log (\ log (n))} <5,26,146 mila $

Answer 1

Non dimenticare che $ \ log n $ cresce ancora in modo esponenziale (in $ \ log (n) $) più veloce di $ \ log (\ log n) $!

In effetti, se si guarda al quoziente di $ \ log (n) $ e $ \ log (\ log (n)) $, non c'è molto impressionante vedere:

^{[ fonte ]}

Ma ancora, si ottiene un fattore di 5-6 per le dimensioni fino a $ 100000 $ Di. Nota che le dimensioni più grandi non sono infrequenti nella pratica, e un aumento di velocità da quel fattore è impressionante ! Può fare la differenza tra l'avere risultati dopo il pranzo o solo domani. Essere consapevoli del fatto che parte del l'aumento di velocità può essere mangiata dai maggiori costanti della realizzazione dell'albero; si dovrebbe plot (o analizzare) $ c \ cdot \ log (n) $ e $ d \ cdot \ log (\ log (n)) $ con $ C, D $ le costanti di runtime attuali per avere un quadro reale.

Inoltre, ciò che Dave cita è importante: se l'operazione ha accelerato questa convenzione viene eseguito, ad esempio, in modo lineare, spesso, incrementi nella velocità costanti diventano incrementi nella velocità lineare, vale a dire che si può diminuire la costante principale del vostro intero algoritmo! Come ho detto sopra, che è impressionante. Basta guardare a cosa succede se si esegue l'operazione di $ n $ volte:

^{[ fonte ]}

Ora, se questo non è vale la pena, non so che cosa.

Answer 2

Si potrebbe immaginare che la differenza di complessità non importa così tanto, e che l'attuale fase di esecuzione è più importante. Ma se l'algoritmo è al centro di un altro algoritmo, allora questa differenza può essere importante.

Da uno scopo puramente teorico, la differenza ovviamente non importa, soprattutto se l'algoritmo è una parte di un altro. Può mettere l'algoritmo più grande in una diversa classe di complessità.

Answer 3

In realtà ho benchmark il furgone Emde Boas albero me una volta. Ho confrontato con un albero di AA, un hashmap e una matrice di bit.

I test svolgono inserti size con numeri casuali in [0, bound] intervallo, poi ricerca size, quindi elimina size e poi ancora ricerche size. Elimina sono fatto su numeri casuali e, quindi bisogna prima capire se sono nella struttura a tutti.

Ecco i risultati (size = 2000000, bound = 10000000) in secondi:

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

Come si può vedere, alberi van Emde Boas sono circa due volte più lento mappe hash, dieci volte lento come array di bit, e 5 volte più velocemente alberi binari di ricerca.

di esigenze Naturalmente il sopra un disclaimer:. I test sono artificiali, si può eventualmente migliorare il codice o di utilizzare una lingua diversa con un compilatore la cui uscita è più veloce, e così via e così via

Questa responsabilità è il cuore della ragione per cui usiamo analisi asintotica in algoritmi di progettazione: come non avete idea di quello che le costanti sono e come le costanti può cambiare a seconda di fattori ambientali, il meglio che possiamo fare è un'analisi asintotica.

Ora, nel caso di $ \ log n $ contro $ \ log \ log n $: nell'esempio di cui sopra, il mio albero van Emde Boas è in grado di contenere $ di 2 ^ {32} $ elementi. $ \ Log 2 ^ {32} = 32 $ e $ \ log 32 = 5 $, che è un fattore 6 miglioramento, che è un po 'in pratica. Inoltre, gli alberi van Emde Boas hanno buoni fattori costanti (è tutta una questione fattori costanti in pratica, per le differenze questo piccolo) e che non hanno bisogno di bilanciare se stessi.