Hogyan állapítom meg egy algoritmus bonyolultságát?

Úgy, hogy bemenet függvényében kiszámolod, hogy hány lépés lesz az algoritmus.

Pl. tipikus probléma: van két tömböd, A és B, meg kell keresni A azon elemeit, amik B-ben nincsenek benne(magyarul különbség).

Ekkor ugye a két tömb mérete m és n, nyilvánvaló, hogy minden A-beli m-re végig kell nézned, hogy benne van e B-ben, tehát n*m lépés szükséges.

Ha egyszerűsítjük a feladatot úgy, hogy mondjuk m=n, akkor világos, hogy ez egy O(n^2), azaz négyzetes futási idejű algoritmus.

Vagy pl. ott van a lineáris keresés algoritmusa:

ez ugye n nagyságú elem esetén a legrosszabb esetben n lépést igényel, tehát ez O(n), azaz lineáris.

Gyorskeresés:

n elemre maximum log2n(azaz 2es alapú logaritmus n) lépésben megtalálja a keresett elemet, tehát ez O(log n).

Az nem bonyolultság hanem futási idő.

[link]