Ha egy algoritmus idő komplexitása összetett, hogyan állítjuk meg hogy beletartozik a pl.: O(n^2) osztályba?

Kifejted az egzakt képletet, megkeresed az aszimptotikusan domináns tagját, és megnézed hogy n^2-nél kisebb-e (azaz c*n^2 "túlnövi-e" n->végtelen esetén valamely c-re). Ha igen, akkor O(n^2) osztályba tartozik. Persze emellett tartozhat annál szűkebb osztályokba, pl O(n*log(n))-be vagy O(n)-be is.

Érdemes ismerni pár elemi függvény aszimptotikus viszonyát, pl:

konstans < log(log(n)) < log(n) < n^0.001 < n^0.5 < n < n^2 < n^3 < n^999 < e^n < e^e^n stb.

Első példád: (7 + n^3)*log(n^5) = (7 + n^3)*5*log(n), ami aszimptotikusan nagyobb, mint n^3, ami még mindig nagyobb mint n^2, tehát nem O(n^2).

Második: (n+log(n)) * gyök(n + log(n)), ami log(n)<n-t felhasználva aszimptotikusan kisebb, mint 2n*gyök(2n) = 2*gyök(2)*n^1.5, ami még mindig kisebb, mint n^2. Így O(n^2)-be tartozik.

Harmadik: n*(200 + log(n)^2) aszimptotikusan kisebb, mint n*(n^0.001 + (n^0.001)^2) ami kisebb mint n^1.01 ami kisebb mint n^2, tehát O(n^2)-be tartozik.

Ismerem annyira a gyakorit, hogy tudjam, hogy le leszek pontozva, de ne tévesszen meg: helyes a válaszom, csak elfelejtettem már a szakszavakat és szép definíciókat. Remélem a lényeg átment.

Nem egy darab kritérium van, amit csak ellenőrzünk, hanem minden ilyen kifejezést a rá jellemző azonosságokkal kell átalakítani. Az alapvető összefüggéseket pedig - például, hogy polinom/exponenciális alakú kifejezés nullához tart - előre tanulnod kellett (volna) analízisből.

Végső soron a függvényosztályok definícióihoz nyúlunk vissza, ha a kérdéses függvény kivételes alakú és másként nem megy.