3.3. Jó és jobb algoritmusok

Ugyanaz a számítási probléma több különböző algoritmussal is megoldható. Például az elkövetkező órákon több rendezési algoritmust is megvizsgálunk. Hogyan lehet az algoritmusok közül választani?

Kisérletek: az egyes algoritmusok implementációt különböző adatokon teszteljük, s a futási eredmények alapján döntünk.

Elméleti vizsgálat: matematikai módszerekkel meghatározzuk az adott algoritmus számára szükséges erőforrásokat (a végrehajtási időt, vagy az elfoglalt tárterületet), mint a bemenő adatok függvényét.

Elméleti vizsgálódáshoz mind az inputot, mind a végrehajtási időt számszerűsíteni kell.

Bemenet mérete: függ a probléma típusától: lehet az adatok száma (rendezés); lehet az adat mérete (például bit a prímtesztnél). Gyakran több módon is mérhetjük a bemenetet, például tekinthetjük a gráf méretének a gráf csúcsainak vagy az éleinek számát.

Futási idő: Lehetőség szerint gépfüggetlen jelölést szeretnénk használni. Ilyen lehet például a végrehajtott lépések (elemi utasítások) száma. A leggyakrabban vizsgált mennyiségek: legjobb érték, legrosszabb érték, átlagos érték, azaz minimálisan, maximálisan és átlagosan hány lépést kell végrehajtani az n méretú inputok esetén. A gyakorlatban talán az átlagos érték lenne a legjobban használható, de ezt gyakran nagyon nehéz pontosan meghatározni. A legrosszabb értéket rendszerint könnyebben meghatározhatjuk, s ez az érték egy pontos felső korlátot ad minden egyes futásra. Bizonyos algoritmusoknál ez az eset igen gyakran előfordul, tehát ekkor közel áll az átlagos értékhez.