3.4. Kis ordó és nagy ordó

Milyen kapcsolatban áll a futási idő az input méretével, amikor ez a méret a végtelenbe tart? Tudjuk-e a futási idő függvényét valamilyen egyszerűbb függvénnyel becsülni, felülről korlátozni?

Az O(f(n)) jelölést (nagy ordó) rendszerint pozitív egész n-eken értelmezett f függvény esetén használjuk. Nem valami határozott mennyiséget jelöl, AzO(f(n)) jelölés az n-től függő mennyiségek becslésére szolgál. Egy X mennyiség helyére akkor írhatunk O(f(n))-t, ha létezik olyan konstans, mondjuk M, hogy minden elég nagy n-re,|X| M ˇ |f(n)|, azaz aszimptotikusan felső becslést adunk egy konstansszorzótól eltekintve a lépésszámra. A definíció nem adja meg az M konstans értékét, és hogy honnan számít nagynak az n. Ezek különböző esetekben más és más értékek lehetnek.

3.1. példa - 1. példa

Mutassuk meg, hogy n2 2 − 3n = O(n2)! A definíció szerint |n2 2 − 3n| M|n2|. Ha n 6, elhagyhatjuk az abszolútértékeket. Kis átalakítások után a 3n ( 1 2 −M)n2 egyenlőtlenséget kapjuk. Ha M 1 2 , akkor a feltétel teljesül, tehát n ≥ 6 esetén létezik a feltételeket kielégítő M konstans.


3.2. példa - 2. példa

Mutassuk meg, hogy nem teljesül a 6n3 = O(n2)! Pozitív n esetén a 6n3 Mn2 egyenlőtlenséget kellene belátnunk. Átalakítás után ebből n M 6 származtatható, tehát adott M érték esetén n értéke nem lehet tetszőlegesen nagy, ellentétben az eredeti feltételekkel.


A gyakorlatban előforduló feladatok bonyolultsága rendszerint az alábbi osztályok valamelyikébe esik. A bonyolultsági osztályok hagyományos jelölését a szokásos elnevezés követi, majd a listát pár adott bonyolultságú feladat zárja.

O(1): konstans idő: egyszerű értékadás, írás/olvasás veremből

O(ln(n)): logaritmikus: bináris keresés rendezett tömbben, elem beszúrása, törlése bináris fából, kupacból (heap)

O(n): lineáris: 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

O(n ˇ ln(n)): quicksort, összefésüléses rendezés.

O(n2): négyzetes: egyszerű rendezési algoritmusok (pl. buborékrendezés), nem rendezett listában az ismétlődések megtalálása

O(cn): exponenciális: hanoi torony, rekurzív Fibonacci számok, n elem permutációinak előállítása

A nagy ordó definíciójában elegendő volt egy adott konstanst találni, melyre az összefüggés igaz. Ha ezt az összefüggést minden pozitív konstansra megköveteljük, akkor a kis ordó definícióját kapjuk. 2n2 = O(n2) és 2n = O(n2) egyaránt teljesül, viszont 2n2 = o(n2) nem teljesül, míg 2n = o(n2) igen. A kis ordó jelölés éles aszimptotikus felső becslést jelöl, s ha f(n) = o(g(n)), akkor a limn!1 f(n) g(n) = 0 összefüggés is fennáll.