6. óra
2005. 11. 14. (Fehér Gábor)
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...