Waarom is het logboek in de big-O van binair zoeken niet basis 2?

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

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.

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *