Új vagyok a számítógépes algoritmusok megértésében. Megértem a bináris keresés folyamatát, de van egy kis félreértésem a hatékonyságával kapcsolatban.
$ s = 2 ^ n $ elem nagyságában átlagosan $ n $ kellene lépéseket egy adott elem megtalálásához. Ha mindkét oldal 2-es alapú logaritmusát vesszük, akkor $ \ log_2 (s) = n $ lesz. Tehát a bináris keresési algoritmus átlagos lépéseinek száma nem lenne $ \ log_2 (s) $?
Ez a Wikipedia cikk a bináris keresési algoritmus szerint az átlagos teljesítmény $ O (\ log n) $. Miért van ez? Miért nem ez a szám $ \ log_2 (n) $?
Megjegyzések
- Másolat az SO-n – A nagy O (logn) naplóalap e?
Válasz
Amikor megváltoztatja a logaritmus alapját, a kapott kifejezés csak egy állandó tényezőtől különbözik, amely A Big-O jelölés definíciója azt jelenti, hogy mindkét funkció ugyanazon osztályba tartozik aszimptotikus viselkedésük tekintetében.
Például $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ ahol $ C = \ frac {1} {\ log_ {2} 10} $.
Tehát a $ \ log_ {10} n $ és a $ \ log_ {2} n $ állandó $ C $ értékkel különböznek egymástól, ezért mindkettő igaz: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {is} O (\ log_ {10} n) $$ Általában $ \ log_ {a} {n} $ $ O (\ log_ {b} {n}) $ pozitív $ 1 $ és $ b $ egész számoknál nagyobb, mint 1.
Egy másik érdekes tény a logaritmikus függvényekkel, hogy míg állandó $ k > 1 $ esetén a $ n ^ k $ NEM $ O (n) $, hanem $ \ log {n ^ k} $ értéke $ O (\ log {n}) $, mivel $ \ log {n ^ k} = k \ log {n} $, amely csak $ állandó tényezővel tér el a $ \ log {n} $ értéktől k $.
Megjegyzések
- Nem csak pozitív egész számokra: Minden valódi $ a, b > 1 $, pl $ e $.
- Hozzáteszem, hogy ez az oka annak, hogy a nagy O jelöléssel a logaritmus alapja általában nincs meghatározva. Ez azt is jelenti, hogy nincs zavar, hogy a $ O (\ log n) $ melyik bázist használja: lehet bármelyik általánosan használt alapú, mivel nem tesz különbséget '.
Válasz
A fade2black válaszai mellett (ami teljesen helyes) érdemes megjegyezni hogy a “$ \ log (n) $” jelölés kétértelmű. Az alap valójában nincs megadva, és az alapértelmezett alap a kontextus alapján változik. A tiszta matematikában az alapot szinte mindig feltételezzük, hogy $ e $ (hacsak nincs megadva), míg bizonyos mérnöki kontextusokban 10 lehet. , a 2. alap annyira elterjedt, hogy a $ \ log $ -ot gyakran 2-esnek tekintik. Ez a wikipédia-cikk soha nem mond semmit az alapról.
De, amint már bemutattuk, ebben az esetben nem ” végül nem számít.
Megjegyzések
- Akkor érdemes még megjegyezni, hogy míg a " log (n) " kétértelmű lehet, hogy " O (log (n)) " nem azért, mert az utóbbinak csak egy jelentése van, függetlenül attól, hogy milyen alapon gondolkodik.