Bináris keresés futási ideje

Tudjuk, hogy egy $n$n elemű tömb esetében a lineáris keresés legrosszabb esetben $n$n-szer tippel. Ösztönösen érezheted úgy, hogy valószínűleg a bináris kereséshez kevesebb találgatás kell, mint a lineáris kereséshez. Valószínűleg arra is rájöttél, hogy a lineáris keresés és a bináris keresés maximális lépésszáma közötti különbség a tömb hosszának növekedésével egyre markánsabbá válik. Vizsgáljuk meg, hogyan tudjuk elemezni a bináris kereséshez maximálisan szükséges lépésszámot!

A kulcsfontosságú gondolat az, hogy amikor a bináris keresés hibásan tippel, akkor a lehetséges válaszokat tartalmazó tömb legalább a felével csökken. Ha a lehetséges válaszok száma 32, akkor a hibás tipp azt legalább 16-ra csökkenti. A bináris keresés minden hibás keresés esetén megfelezi a tartományt.

Ha 8 hosszúságú tömbbel indítunk, akkor a hibás tippek a lehetséges válaszok tartományát először 4 hosszúságúra, majd 2-re, ezután 1-re csökkentik. Amikor a tartomány 1 elemet tartalmaz, akkor nincs szükség több tippre; az adott elem vagy megfelelő, vagy nem, és ezáltal végeztünk. 8 hosszúságú tömb esetén a bináris keresésnek maximum négy tippelés kell.

Mit gondolsz, mi a helyzet egy 16 elemű tömb esetében? Ha az a válaszod, hogy az első tipp legalább 8 elemet ki fog zárni, ezután maximum 8 marad, akkor képben vagy. Ebből az következik, hogy 16 elem esetében maximum 5 tipp kell.

Mostanra már kirajzolódott a minta. Mindig, amikor megduplázzuk a tömb méretét, maximum eggyel több tippre van szükségünk. Tegyük fel, hogy maximum $m$m tipp kell egy $n$n hosszúságú tömbhöz. Akkor egy $2n$2, n hosszúságú tömbhöz az első tipp a lehetséges tippek tartományát $n$n-re csökkenti, amihez $m$m maximális tipp tartozik, így a tömbünkhöz összesen $m+1$m, plus, 1 tipp kell maximálisan.

Vizsgáljunk meg általános esetben egy $n$n hosszúságú tömböt! Meghatározhatjuk úgy a maximálisan szükséges tippek számát, mint „az a szám plusz egy, ahányszor az $n$n-et ismételten félbe tudjuk osztani, amíg nem kapunk 1-et.” De ezt nem kényelmes így leírni.

Szerencsére létezik egy olyan matematikai függvény, ami az $n$n ismételt félbeosztását jelenti, amíg nem érjük el az 1-et: ez a 2-es alapú logaritmus $n$n. Ezt leggyakrabban így írják: $\log_2 n$log, start base, 2, end base, n, de így is találkozhatsz vele az informatika területén: $\lg n$\lg, n. (Szeretnéd átnézni a logaritmust? Itt többet megtudhatsz.)

Íme egy táblázat a különböző $n$n-ek 2-es alapú logaritmusával:

Ezt a táblázatot grafikonon ábrázolva ezt kapjuk:

Kinagyítva n kisebb értékeire:

A logaritmus függvény nagyon lassan nő. A logaritmus az exponenciális függvény inverze, ami viszont nagyon gyorsan nő, úgyhogy ha $\log_2 n = x$log, start base, 2, end base, n, equals, x, akkor $n = 2^x$n, equals, 2, start superscript, x, end superscript. Például mivel $\log_2 128 = 7$log, start base, 2, end base, 128, equals, 7, tudjuk, hogy $2^7 = 128$2, start superscript, 7, end superscript, equals, 128.

Ez megkönnyíti a bináris keresés futási idejének kiszámítását akkor, ha $n$n 2 pontos hatványa. Ha $n$n értéke 128, akkor a bináris keresésnek maximum 8 lépésre van szüksége ($\log_2 128 + 1$log, start base, 2, end base, 128, plus, 1).

Mi van abban az esetben, ha $n$n nem a 2 hatványa? Ekkor megkeressük 2-nek a legközelebbi lefelé kerekített hatványát. Például egy 1000 hosszúságú tömb esetében a legközelebbi lefelé kerekített hatvány az 512, ami $2^{9}$2, start superscript, 9, end superscript. Ez alapján azt becsüljük, hogy $\log_2 1000$log, start base, 2, end base, 1000 egy olyan szám, ami nagyobb, mint 9 és kisebb, mint 10. Ha számológéppel kiszámoljuk, akkor körülbelül 9,97-et kapunk. Hozzáadva egyet, az eredmény 10,97. Tört esetén lefelé kerekítünk, hogy megkapjuk a szükséges tippek számát. Ebből következik, hogy egy 1000 elemű tömbben a bináris keresés maximum 10 keresést hajt végre.

A Tycho-2 csillagkatalógus 2 539 913 csillagjához a 2 legközelebbi hatványa $2^{21}$2, start superscript, 21, end superscript (ami 2 097 152), ezért maximum 22 keresésre van szükségünk. A lineáris keresésnél sokkal jobb!

Hasonlítsd össze $n$n-t és $\log _{2} n$log, start base, 2, end base, n-t!

A következő részben megvizsgáljuk, hogy az informatikában hogyan jellemzik a lineáris és a bináris keresés futási idejét olyan jelölési rendszer segítségével, mely összegzi a futási idő legfontosabb összetevőit és elhanyagolja a kevésbé fontosakat.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.