Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.8. Az algoritmus hatékonysági jellemzői

1.8. Az algoritmus hatékonysági jellemzői

Amikor egy algoritmust keresünk egy feladat megoldására a következő két kérdés fel kell, hogy vetődjön:

[1.] Megoldható-e a probléma és ha igen, akkor egy vagy több megoldása van-e? (Ezt hívják a megoldás problémájának.)

[2.] Ha már találtunk a problémára megoldási algoritmust, akkor van-e a meglévőnél hatékonyabb másik megoldási algoritmus? (A megoldási módszer, algoritmus problémája.)

A második kérdés csak akkor jogos, ha a megoldás létezik. Meghatározásra szorul az, hogy mit értünk egy megoldó algoritmus hatékonyságán, mikor mondhatjuk, hogy egy probléma egyik megoldó algoritmusa hatékonyabb, mint a másik. Az is tisztázandó, hogy milyen szempont szerint tekintjük a hatékonyságot. A hatékonyságot mérőszámmal lehet jellemezni. Kiválasztva a mérlegelési szempontot, amely alapján az algoritmust vizsgáljuk, az algoritmus minden bemenő adatára egy mérőszámot konstruálunk. Az az algoritmus a hatékonyabb egy rögzített input esetén, amelyikre ez a mérőszám a jobb eredményt adja. Mérlegelési szempontnak általában az algoritmus időigényét (lépésszámát, műveletszámát) szokás tekinteni, hiszen az időnek vagyunk általában szűkében. Nem elhanyagolható azonban egy másik szempont sem, az algoritmus tárigénye a számítógépes realizáció szempontjából. Egy algoritmus lehet egy bizonyos inputra jobb, mint egy másik algoritmus, egy másik input esetében pedig lehet rosszabb. Ezért a hatékonysági mérőszám fogalmát egy kicsit árnyaltabban kell megközelíteni. Először is be kell vezetni az inputok összehasonlítására alkalmas valamiféle mérőszámot. Teljesen nyílvánvaló, hogy például egy százjegyű számból általában tovább tart négyzetgyököt vonni, mint egy tízjegyűből. Be kell tehát vezetni a probléma méretének a fogalmát.

1.17. Definíció. Az algoritmus inputjának a mérete (problémaméret)

Legyen adott egy probléma, amely megoldható egy algoritmussal. Legyen az algoritmus lehetséges inputjainak a halmaza. Legyen egy input. Az input méretének nevezzük az konkrét megadásakor használt bitek számát. Ez egy nemnegatív egész szám, mérőszám. Jelölésben az input mérete .

Meglepő, de ez a bizonytalannak, nem egészen egyértelműnek tűnő méretdefiníció mégis hatékony fogalomnak bizonyul.

1.19. Példa. A négyzetgyökvonó algoritmusunk inputja legyen az egyszerűség kedvéért az pozitív egész szám, amelyből gyököt akarunk vonni. Ekkor az algoritmus inputjának mérete , a számot leíró bitek száma.

Vezessünk be most néhány jelölést. Legyen egy algoritmus, az algoritmus összes lehetséges input adatainak a halmaza és egy lehetséges input. Az input esetén -szel fogjuk jelölni az algoritmus probléma megoldási (-time, idő) és -szel a (-storage, tár).

1.18. Definíció. Az algoritmus időbonyolultsága

A

számot az A algoritmus nak nevezzük.

Az időbonyolultság megadja, hogy az -nél nem nagyobb méretű inputok esetén mennyi a legnagyobb időigény.

1.19. Definíció. Az algoritmus tárkapacitás bonyolultsága

Az

számot az A algoritmus nak nevezzük.

A tárkapacitás bonyolultság megadja, hogy az -nél nem nagyobb méretű inputok esetén mennyi a legnagyobb tárigény.

Mindkét mérőszám hatékonysági mérőszám. A gyakorlatban ma már inkább az elsőt használják algoritmusok hatékonyságának az összehasonlításában, ami nem csökkenti a második szerepének a fontosságát. Elég nagy méretű tárak állnak ma már rendelkezésre, de nincs olyan tár, amit pillanatok alatt ki ne lehetne nőni egy "ügyes" algoritmussal. Láthatóan a bonyolultságok a probléma méretének monoton növekedő függvényei és az adott méretet meg nem haladó méretű esetek közül a legrosszabb esettel jellemzik az algoritmust. Ha ugyanazon probléma megoldására két vagy több algoritmus is létezik, akkor a közülük történő választás megalapozásához ad segítséget az algoritmusok bonyolultsági függvényeinek a vizsgálata, összehasonlítása. Az egyes bonyolultságok összehasonlítása az egyes függvények növekedési ütemének, rendjének az összehasonlítását jelenti, mely fogalmat alább definiáljuk. A fenti mérőszámoknak létezik olyan kevésbé pesszimista változata is amikor a legrosszabb eset helyett az inputok szerinti átlagolt értéket vesszük, vagy ami realisztikusabb, hogy ismerve az egyes inputok gyakoriságát (valószínűségét) súlyozott átlagot (várható értéket) számolunk. Ez utóbbi nem tartozik az anyagunkhoz, mivel valószínűség-számítási ismereteket (sajnos) nem tételezünk föl.