Algoritmikus komplexitás

A HupWiki-ből...

Az algoritmusok hatékonyságának (komplexitásának) szemléltetésére bevezették az O (ordó) operátort. Nézzünk egy példát: képzeljünk el egy láncolt listát vagy egy közönséges tömböt, amelyben egységnyi elem van. Az adott elem megtalálásának ideje egyenesen arányos az elemek számával. Ha száz elemből egy másodperc alatt megtaláltuk a keresett elemet, akkor számíthatunk arra, hogy ezer elemnél kb. 10 másodpercig fog tartani a keresés. Az ilyen algoritmust nevezzük O(n)-nek (ejtsd: ordó n), amely az előbb említett egyenes arányú viszonyt, azaz az elemek számával arányos végrehajtási időt jelenti. Minél több elem van, annál hosszabb ideig tart a végrehajtás. Példa az O(n) algoritmusra: lista/tömb végigolvasása, lista/tömb minimális/maximális elemének, elemek átlagának meghatározása, n!, fib(n) kiszámítása

Ezzel szemben az O(1) algoritmus esetén gyakorlatilag szinte konstans idő alatt, azaz elemszámtól függetlenül kb. ugyanannyi ideig tart a keresés. Ezért ezen esetben a keresési algoritmus O(1), azaz konstans. Példa az O(1) algoritmusra: egyszerű értékadás, írás-olvasás veremből.

Általánosan pedig azt mondhatjuk, hogy ha ismert az algoritmus időigényét a bemeneti adatok méretének függvényében leíró polinom, akkor az ordó operátor ennek a polinomnak az aszimptotikusabban leggyorsabban növekvő tagját jelenti, konstansszorzók nélkül. Leggyakrabban ez megegyezik a legnagyobb kitevőjű taggal (például 4*n^6 + 7*n^3 = O(n^6)), de nem mindig. Az exponenciális tagok például gyorsabban nőnek a hatványoknál, úgyhogy 2^n + n^100 + log(n) = O(2^n). Példa exponenciális időigényű algoritmusra: brute-force keresés (minden lehetőség végigpróbálgatása).

Személyes eszközök