V porozumění algoritmům počítačové vědy jsem nový. Rozumím procesu binárního vyhledávání, ale mám mírné nedorozumění s jeho účinností.
Ve velikosti prvků $ s = 2 ^ n $ by to v průměru trvalo $ n $ kroky k vyhledání konkrétního prvku. Vezmeme-li základní 2 logaritmus obou stran, získáme $ \ log_2 (s) = n $. Takže průměrný počet kroků pro binární vyhledávací algoritmus by nebyl $ \ log_2 (s) $?
Tento článek na Wikipedii binární vyhledávací algoritmus říká, že průměrný výkon je $ O (\ log n) $. Proč tomu tak je? Proč není toto číslo $ \ log_2 (n) $?
Komentáře
- Duplikovat na SO – Je základna protokolu Big O (logn) e?
Odpověď
Když změníte základ logaritmu, výsledný výraz se bude lišit pouze o konstantní faktor, který o definice zápisu Big-O znamená, že obě funkce patří do stejné třídy s ohledem na jejich asymptotické chování.
Například $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ kde $ C = \ frac {1} {\ log_ {2} 10} $.
Takže $ \ log_ {10} n $ a $ \ log_ {2} n $ se liší konstantou $ C $, a proto platí obě: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {is} O (\ log_ {10} n) $$ Obecně $ \ log_ {a} {n} $ je $ O (\ log_ {b} {n}) $ pro kladná celá čísla $ a $ a $ b $ větší než 1.
Další zajímavý fakt s logaritmickými funkcemi je, že zatímco pro konstantní $ k > 1 $, $ n ^ k $ NENÍ $ O (n) $, ale $ \ log {n ^ k} $ je $ O (\ log {n}) $ od $ \ log {n ^ k} = k \ log {n} $, které se liší od $ \ log {n} $ pouze konstantním faktorem $ k $.
Komentáře
- Nejen pro kladná celá čísla: Pro všechna skutečná $ a, b > 1 $, např $ e $.
- Dodal bych, že to je důvod, proč u notace big-O není základ logaritmu běžně specifikován. Znamená to také, že není pochyb o tom, která základna $ O (\ log n) $ používá: může to být kterýkoli z běžně používaných základů, protože to ' nezmění.
Odpověď
Kromě odpovědi fade2black (která je zcela správná) stojí za zmínku že zápis „$ \ log (n) $“ je nejednoznačný. Základna není ve skutečnosti specifikována a výchozí základna se mění na základě kontextu. V čisté matematice se základ téměř vždy předpokládá jako $ e $ (pokud není specifikován), zatímco v určitých technických kontextech by to mohlo být 10. V počítačové vědě , základna 2 je tak všudypřítomná, že $ \ log $ se často považuje za základnu 2. Tento článek na wikipedii nikdy neříká nic o základně.
Ale jak již bylo ukázáno, v tomto případě to není “ Nakonec na tom nezáleží.
Komentáře
- Pravděpodobně dále stojí za zmínku, že zatímco " se přihlaste (n) " může být nejednoznačné, že " O (log (n)) " není to proto, že ten druhý má pouze jeden význam, bez ohledu na to, na jakou základnu byste mohli myslet.