Aszimptotikus jelölés

Az előzőekben a lineáris és bináris keresést olyan szempontból elemeztük, hogy mekkora a maximálisan szükséges tippek száma. De a kérdés valójában az, hogy mennyi ideig futnak ezek az algoritmusok. Minket az idő érdekel, nem pusztán a tippek száma. A lineáris és bináris keresés futási idejébe az az idő is beletartozik, ami ahhoz kell, hogy kiszámoljuk és megvizsgáljuk a tippet, de más dolgokat is figyelembe kell venni.

Egy algoritmus futási ideje attól függ, hogy a számítógépnek mennyi időre van szüksége az algoritmushoz tartozó programsorok lefuttatásához – és ez függ a számítógép sebességétől, a programnyelvtől, attól, hogy mennyi időre van szüksége a fordítóprogramnak a programsorokat a programozási nyelvről a gépen közvetlenül futni tudó gépi kódra való átalakításhoz és egyéb tényezőktől is.

Gondoljuk végig alaposabban, mit is jelent egy algoritmus futási ideje. Két gondolatot kapcsolunk itt össze. Először is meg kell határozni, hogy az algoritmusnak az input méretének függvényében mennyi időre van szüksége. Ez észszerűnek tűnik, nem? Azt már láttuk, hogy mind a lineáris, mind a bináris keresés esetében a maximálisan szükséges keresések száma a tömb méretének növekedésével megnő. Vagy gondolj a GPS-re! Ha csak az autópályákat venné figyelembe, akkor gyorsabban megtalálná az útvonalat, mint így, hogy minden kis út szerepel benne, nem? Tehát az algoritmus futási idejét az input méretének függvényeként határozhatjuk meg.

A másik gondolat alapján azt vizsgáljuk meg, hogy milyen gyorsan növekszik a függvény az input méretétől függően. Ezt a futási idő növekedési rátájának hívjuk. Hogy a dolog könnyen kezelhető legyen, csupaszítsuk le a függvényt legfontosabb elemeire, és hagyjuk ki a kevésbé fontos részeket. Például tegyük fel, hogy egy algoritmus egy $n$n elemű inputtal $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 gépi utasítást hajt végre. A $6n^2$6, n, squared tényező jobban fog növekedni, mint a maradék $100 n + 300$100, n, plus, 300, ha az $n$n – jelen esetben 20 – elég nagy. Az alábbi grafikonon a $6n^2$6, n, squared és a $100n + 300$100, n, plus, 300 értékeit ábrázoltuk az $n$n [0;100] intervallumban:

Ebben az esetben azt mondjuk, hogy az algoritmus futási ideje $n^2$n, squared-tel nő, figyelmen kívül hagyva a 6-os szorzót és a maradék $100n + 300$100, n, plus, 300 koefficienseket. Nem igazán érdekesek maguk a konkrét együtthatók – ha a futási időt $an^2 + bn + c$a, n, squared, plus, b, n, plus, c írja le, valamilyen $a > 0$a, is greater than, 0, $b$b és $c$c értékekkel, mindig lesz olyan $n$n érték, ahol $an^2$a, n, squared nagyobb lesz, mint $bn + c$b, n, plus, c, és ez a különbség $n$n növekedésével egyre nagyobb lesz. Például az alábbi grafikon $0{,}6n^2$0, comma, 6, n, squared és $1000n + 3000$1000, n, plus, 3000 értékeit mutatja, ahol tizedére csökkentettük $n^2$n, squared szorzóját és a másik két tényezőt megtízszereztük:

Megnőtt az az $n$n érték, ahol $0{,}6n^2$0, comma, 6, n, squared nagyobbá válik, mint $1000n + 3000$1000, n, plus, 3000, de mindig lesz egy ilyen pont, függetlenül attól, hogy a konstansoknak milyen értéket adunk.

Azáltal, hogy elhagytuk a kevésbé szignifikáns tényezőket és a konstansokat, összpontosíthatunk az algoritmus futási idejét lényegesen befolyásoló tényezőre – és annak növekedésére – anélkül, hogy elmerülnénk a részletekbe, amik csak megzavarnának. Amikor elhagyjuk a konstans tagokat és a kevésbé fontos tényezőket, aszimptotikus komplexitásról beszélünk. Három fajtájával fogunk megismerkedni: a $\Theta$\Theta, az O (ordó) és az $\Omega$\Omega jelöléssel.

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