NézetNyomtat

6. óra
Címkék > Óra

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...

Feladat