Ik ben nieuw in het begrijpen van computerwetenschappelijke algoritmen. Ik begrijp het proces van de binaire zoekopdracht, maar ik heb een klein misverstand over de efficiëntie ervan.
In een grootte van $ s = 2 ^ n $ -elementen zou het gemiddeld $ n $ kosten stappen om een bepaald element te vinden. Als we de logaritme met grondtal 2 van beide zijden nemen, levert dit $ \ log_2 (s) = n $ op. Zou het gemiddelde aantal stappen voor het binaire zoekalgoritme dus niet $ \ log_2 (s) $ zijn?
Dit Wikipedia-artikel op het binaire zoekalgoritme zegt dat de gemiddelde prestatie $ O (\ log n) $ is. Waarom is dit zo? Waarom is dit nummer niet $ \ log_2 (n) $?
Reacties
- Dupliceren op SO – Is Big O (logn) logboekbasis e?
Answer
Wanneer u de logaritme wijzigt, verschilt de resulterende uitdrukking alleen met een constante factor die, met definitie van Big-O-notatie , impliceert dat beide functies tot dezelfde klasse behoren met betrekking tot hun asymptotische gedrag.
Bijvoorbeeld $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ waarbij $ C = \ frac {1} {\ log_ {2} 10} $.
Dus $ \ log_ {10} n $ en $ \ log_ {2} n $ verschillen constant $ C $, en dus zijn beide waar: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {is} O (\ log_ {10} n) $$ In het algemeen is $ \ log_ {a} {n} $ $ O (\ log_ {b} {n}) $ voor positieve gehele getallen $ a $ en $ b $ groter dan 1.
Een ander interessant feit met logaritmische functies is dat terwijl voor constante $ k > 1 $, $ n ^ k $ NIET $ O (n) $ is, maar $ \ log {n ^ k} $ is $ O (\ log {n}) $ sinds $ \ log {n ^ k} = k \ log {n} $ dat verschilt van $ \ log {n} $ door alleen de constante factor $ k $.
Reacties
- Niet alleen voor positieve gehele getallen: voor alle echte $ a, b > 1 $, bijv $ e $.
- Ik zou eraan willen toevoegen dat dit de reden is waarom bij de big-O-notatie de basis van de logaritme gewoonlijk niet wordt gespecificeerd. Het betekent ook dat er geen verwarring bestaat over welke basis $ O (\ log n) $ gebruikt: het kan elke veelgebruikte basis zijn, aangezien ' geen verschil maakt.
Antwoord
Naast het antwoord van fade2black (dat helemaal correct is), is het vermeldenswaard dat de notatie “$ \ log (n) $” dubbelzinnig is. De basis is niet echt gespecificeerd en de standaardbasis verandert op basis van de context. In zuivere wiskunde wordt bijna altijd aangenomen dat de basis $ e $ is (tenzij gespecificeerd), terwijl het in bepaalde technische contexten 10 kan zijn. , is basis 2 zo alomtegenwoordig dat $ \ log $ vaak wordt verondersteld basis 2 te zijn. Dat wikipedia-artikel zegt nooit iets over de basis.
Maar, zoals al is aangetoond, doet het in dit geval niet ” Het maakt niet uit.
Reacties
- Het is waarschijnlijk verder de moeite waard om op te merken dat terwijl " log (n) " kan dubbelzinnig zijn dat " O (log (n)) " is niet omdat de laatste maar één betekenis heeft, ongeacht de basis waaraan u denkt.