Non conosco gli algoritmi di informatica. Comprendo il processo di ricerca binaria, ma ho un leggero malinteso riguardo alla sua efficienza.
In una dimensione di $ s = 2 ^ n $ elementi, occorrerebbe, in media, $ n $ passaggi per trovare un elemento particolare. Prendendo il logaritmo in base 2 di entrambi i lati si ottiene $ \ log_2 (s) = n $. Quindi il numero medio di passaggi per lalgoritmo di ricerca binaria non sarebbe $ \ log_2 (s) $?
Questo articolo di Wikipedia su lalgoritmo di ricerca binaria dice che la prestazione media è $ O (\ log n) $. Perché è così? Perché non è questo numero $ \ log_2 (n) $?
Commenti
- Duplica su SO – Big O (logn) log base e?
Risposta
Quando si modifica la base del logaritmo, lespressione risultante differisce solo per un fattore costante che, per definizione di notazione Big-O , implica che entrambe le funzioni appartengano alla stessa classe rispetto al loro comportamento asintotico.
Ad esempio $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ dove $ C = \ frac {1} {\ log_ {2} 10} $.
Quindi $ \ log_ {10} n $ e $ \ log_ {2} n $ differiscono di una costante $ C $, e quindi entrambi sono veri: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {è} O (\ log_ {10} n) $$ In generale $ \ log_ {a} {n} $ è $ O (\ log_ {b} {n}) $ per interi positivi $ a $ e $ b $ maggiori di 1.
Un altro fatto interessante con le funzioni logaritmiche è che mentre per la costante $ k > 1 $, $ n ^ k $ NON è $ O (n) $, ma $ \ log {n ^ k} $ è $ O (\ log {n}) $ poiché $ \ log {n ^ k} = k \ log {n} $ che differisce da $ \ log {n} $ solo per il fattore costante $ k $.
Commenti
- Non solo per numeri interi positivi: per tutti i $ a, b reali > 1 $, ad es $ e $.
- Vorrei aggiungere che questo è il motivo per cui con la notazione O grande, la base del logaritmo comunemente non è specificata. Significa anche che non cè confusione su quale base $ O (\ log n) $ usa: può essere una delle basi comunemente usate, dato che ' non fa la differenza.
Risposta
Oltre alla risposta di fade2black (che è completamente corretta), vale la pena notare che la notazione “$ \ log (n) $” è ambigua. La base non è effettivamente specificata e la base predefinita cambia in base al contesto. Nella matematica pura, si presume quasi sempre che la base sia $ e $ (a meno che non sia specificato), mentre in alcuni contesti ingegneristici potrebbe essere 10. In informatica , la base 2 è così onnipresente che spesso si presume che $ \ log $ sia la base 2. Larticolo di wikipedia non dice mai nulla sulla base.
Ma, come è già stato mostrato, in questo caso non lo fa ” finiscono per avere importanza.
Commenti
- Probabilmente vale ulteriormente la pena notare che mentre " log (n) " potrebbe essere ambiguo che " O (log (n)) " non è perché questultimo ha un solo significato, indipendentemente dalla base a cui potresti pensare.