6. óra

Algoritmusok sebessége

• Egy algoritmus futási ideje a végrehajtásához szükséges elemi (konstans idejű) utasítások számával fejezhető ki.
• Ez a szám természetesen függ a bemenetre kapott adatok $n$ számától.
• Minket valójában ez az összefüggés érdekel: vegyünk például egy rendezőalgoritmust, ami $n$ számot $50n^3+600n^2+36\log{\left(n\right)}+2000$ utasítás alatt rendez növekvő sorrendbe.
• (A $2000$ utasítás a rendezendő számok számától függetlenül mindig végrehajtódik.)
• Ha nagyon sok számot kell rendezni, akkor ezek közül a tagok közül az 50$n^3$ fog a leggyorsabban növekedni, és egy idő után a többi tag "elenyészik hozzá képest".
• Tehát egy algoritmus sebessége jól jellemezhető a futási idejének legnagyobb növekedési ütemű tagjával, ami esetünkben $50n^3$
• Az $50$-es konstans szorzó viszont nagyban függ az algoritmus konkrét leprogramozásától, és a fordítóprogramtól, tehát az algoritmusok elméleti értékelésénél nem vesszük figyelembe.
• Tehát ennek az algoritmusnak a futási idejét az $n^3$ számmal jellemezhetjük. Azt mondjuk ilyenkor, hogy az lefut $O\left(n^3\right)$ időben. Tehát ez azt jelenti, hogy a futási ideje $n^3$-el arányos.

Megjegyzések

• A példánkban adott rendezési algoritmus igencsak ügyetlenke, ugyanis az egyszerű cserés rendezés költsége csupán $O\left(n^2\right)$. Ráadásul még annál is létezik gyorsabb algoritmus: Rendezési algoritmusok
• Ha a futási idő $O\left(n\right)$, akkor lineáris algoritmusokról beszélünk, ha $O\left(a_k n^k + a_{k-1}n^{k-1}+...+a_0\right)$, ahol $a_k > 0$ akkor polinomiálisról, ha pedig $O\left( e^n \right) $ akkor exponenciálisról. Az exponenciális is lehet használható, ha csak elég kis $n$-ekkel dolgozunk.
• Versenyeken a leprogramozásra rendelkezésre álló időt is figyelembe kell vennünk...

Feladat