Ha ezt az üzenetet látod, az annak a jele, hogy külső anyagok nem töltődnek be hibátlanul a honlapunkra.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Fő tartalom

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 elemű inputtal 6n2+100n+300 gépi utasítást hajt végre. A 6n2 tényező jobban fog növekedni, mint a maradék 100n+300, ha az n – jelen esetben 20 – elég nagy. Az alábbi grafikonon a 6n2 és a 100n+300 értékeit ábrázoltuk az n [0;100] intervallumban:
Ebben az esetben azt mondjuk, hogy az algoritmus futási ideje n2-tel nő, figyelmen kívül hagyva a 6-os szorzót és a maradék 100n+300 koefficienseket. Nem igazán érdekesek maguk a konkrét együtthatók – ha a futási időt an2+bn+c írja le, valamilyen a>0, b és c értékekkel, mindig lesz olyan n érték, ahol an2 nagyobb lesz, mint bn+c, és ez a különbség n növekedésével egyre nagyobb lesz. Például az alábbi grafikon 0,6n2 és 1000n+3000 értékeit mutatja, ahol tizedére csökkentettük n2 szorzóját és a másik két tényezőt megtízszereztük:
Megnőtt az az n érték, ahol 0,6n2 nagyobbá válik, mint 1000n+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 Θ, az O (ordó) és az Ω 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.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.