Az aszimptotika egy algoritmus futási idejének, hatékonyságának egyszerű leírását adja, valamint lehetővé teszi a szóba jövő algoritmusok relatív teljesítményének összehasonlítását is.

Vegyünk egy példát, amelyen keresztül láthatjuk az algoritmusok futási idejét. Ebben a példában adjuk meg, hogy hány olyan kombinációja van $a,b,c$ pozitív számoknak, amelyek összege $n$ lesz. Nézzünk meg kétféle algoritmust erre a problémára.

Az első esetben naivan nézzünk végig az összes lehetséges kombinációt, amelyre teljesül, hogy $a + b + c = n$.

A második esetben nézzük végig az összes $a, b$ kombinációt és ezzel számoljuk ki a $c$-t, $c = n- (a+b)$. Ha $c$ nagyobb vagy egyenlő, mint 0, akkor ez egy megfelelő kombináció.

Hatékonyság:

Arra a kérdésre, hogy melyik a hatékonyabb megoldás, megmérhetnénk, hogy melyik mennyi ideig fut egy számítógépen, de ezzel az a probléma, hogy mindegyik számítógép más és más, ezért például egy szuperszámítógépen sokkal gyorsabban fog lefutni mind a kettő megoldás, mint egy ősrégi számítógépen.

Ennél egy sokkal jobb megoldás, ha nem a futás idejét mérjük, hanem inkább megszámoljuk, hogy egyes részei a kódnak hányszor futnak le. Ez a megoldás független bármilyen géptől, mivel mindegyik gépen ugyanaz az algoritmus fut le. Ez viszont még mindig nem teljesen jó. Pl. ha tudjuk, hogy $n=20$-ra 9261-szer végzi el az algoritmus az elágazás ellenőrzését, még mindig nem tudjuk, hogy $n=100$, $n = 1000$, $n = 10000$ esetekben ez mennyi. Ezt nem is kell kiszámolnunk, elég, ha általánosítunk bármilyen $n$-re, így láthatjuk, hogy a bemenet növekedésével miként növekszik az algoritmus futási ideje.

Első eset:

Ha az elágazást nézzük, (mivel ez az a sor kód, ami a legtöbbször futhat), $(n+1) \cdot (n+1) \cdot (n+1)$-szer fut le, azaz $(n+1)^3 = n^3 + 3n^2 + 3n + 1$.

Ezt tovább egyszerűsíthetjük, mivel nagyon nagy $n$-ek esetén a domináns tag határozza meg a leginkább a műveletigényt, így a többi tag elhanyagolható. Ezzel ugyan pontatlanabb lesz a számításunk, de sokkal egyszerűbb.

$n^3 + 3n^2 + 3n + 1 \approx n^3$

Második eset:

Ha az elágazást nézzük, (mivel ez az a sor kód, ami a legtöbbször futhat), $(n+1) \cdot (n+1)$-szer fut le, azaz $(n+1)^2 = n^2 + 2n + 1 \approx n^2$.

Aszimptotikus jelölések

Az alábbi jelölések olyan függvényhalmazokat fognak jelölni, amelyekre igaz, hogy olyan $f$ függvényekből állnak, amiket elég nagy $n$ helyettesítési értékekre, megfelelelő pozitív konstans szorzókkal alulról, felülről vagy alulről és felülről is becsül a $g$ függvény.

Theta ( $\Theta$ ):

A $\Theta$ aszimptotikus alsó és felső korlátot ad a függvényre.

$\Theta(g(n)) = \{ \space f(n) \space | \space \exists c_1, c_2 > 0, \space n_0 \geq 0 \space : \space \forall n \geq n_0 \space : \space 0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \space \}$

$f \in \Theta(g)$

Másképp az $f(n)$ függvény hozzátartozik a $\Theta(g(n))$ halmazhoz, ha léteznek $c_1$ és $c_2$ pozitív állandók úgy, hogy $f$ elég nagy $n$-ek esetén "beszorítható" $c_1g(n)$ és $c_2g(n)$ közé. Az $f(n)$ függvény egy állandó szorzótényezőtől eltekintve egyenlő $g(n)$-nel. Ekkor azt mondjuk, hogy $g(n)$ aszimptotikusan éles korlátja $f(n)$-nek.

$f(n) = \frac{n^2}{2} − 3n \in \Theta(n^2)$

$c_1 \cdot n^2 \leq \frac{1}{2} n^2 - 3n \leq c_2 \cdot n^2$

$c_1 \leq \frac{1}{2} - \frac{3}{n} \leq c_2$

Ekkor léteznek olyan $c_1$ és $c_2$ állandók, hogy $f$ "beszorítható" $c_1 \cdot g(n)$ és $c_2 \cdot g(n)$ közé. Lényegében el kell dobni az alacsonyabb rendű tagokat, és figyelmen kívül kell hagyni a legmagasabb rendű tag főegyütthatóját.

$f(n) = an^2 + bn + c \in \Theta(n^2)$

Továbbá bármelyik konstans függvényre, például $\Theta(20)$, fennáll a $\Theta(n^0)$, ami egyenlő $\Theta(1)$-el.

Ordó ( $O$ ):

Az $O$ aszimptotikus felső korlátot ad a függvényre.

$O(g(n)) = \{ \space f(n) \space | \space \exists c > 0, \space n_0 \geq 0 \space : \space \forall n \geq n_0 \space : \space 0 \leq f(n) \leq cg(n) \space \}$

$f \in O(g)$

Minden az $n_0$-nál nagyobb $n$ értékre az $f(n)$ függvényérték $cg(n)$-nel egyenlő vagy annál kisebb. Az $O$ egy állandó tényezőtől eltekintve felső korlátot ad a függvényre. Ha $f(n) \in \Theta(g(n))$, akkor ez maga után vonja $f(n) \in O(g(n))$ teljesülését.

Omega ( $\Omega$ ):

Az $\Omega$ aszimptotikus alsó korlátot ad a függvényre.

$\Omega(g(n)) = \{ \space f(n) \space | \space \exists c > 0, \space n_0 \geq 0 \space : \space \forall n \geq n_0 \space : \space 0 \leq cg(n) \leq f(n) \space \}$

$f \in \Omega(g)$

Minden az $n_0$-nál nagyobb $n$ értékre az $f(n)$ függvényérték $cg(n)$-nel egyenlő vagy annál nagyobb. Ha $f(n) \in \Theta(g(n))$, akkor ez maga után vonja $f(n) \in \Omega(g(n))$ teljesülését.

Bármely két $f(n)$ és $g(n)$ függvény esetén $f(n) \in \Theta(g(n))$ akkor és csak akkor, ha $f(n) \in O(g(n))$ és $f(n) \in \Omega(g(n))$.

Kis ordó ( $o$ ):

A $o$ aszimptotikusan nem éles felső korlát jelölésére használjuk.

$o(g(n)) = \{ \space f(n) \space | \space \forall c > 0 : \exists n_0 \geq 0 \space : \space \forall n \geq n_0 \space : \space 0 \leq f(n) < cg(n) \space \}$

$f \in o(g)$

$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0$

Különbség ordó és kis ordó között:

Az ordóra igaz, hogy $2n \in O(n)$ aszimptotikusan éles felső korlát, mivel létezik olyan szám, (elég ha egy ilyen számot találunk), amellyel megszorozva $n$-t, felső korlátja lesz a $(2n)$-nek, például $c = 3$. Tehát találtunk egy ilyen számot.

Ezzel szemben a kis ordóra $2n \not \in o(n)$, mivel definíció szerint, bármilyen kicsi számot is mondunk, (minden számra teljesülnie kell), egy adott ponttól (küszöbindextől) kezdve felső korlátja lesz a $(2n)$-nek. Viszont, ha azt mondjuk, hogy $c = 1$, akkor már nem teljesül az $f(n) < c \cdot g(n)$ feltétel. Tehát $2n \in o(n^2)$, de $2n \not \in o(n)$.

Kis omega ( $\omega$ ):

A $\omega$ aszimptotikusan nem éles alsó korlát jelölésére használjuk.

$\omega(g(n)) = \{ \space f(n) \space | \space \forall c > 0 : \exists n_0 \geq 0 \space : \space \forall n \geq n_0 \space : \space 0 \leq cg(n) < f(n) \space \}$

$f \in \omega(g)$

$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty$

Míg az omegára igaz, hogy $\frac{n^2}{2} \in \Omega(n^2)$ aszimptotikusan éles alsó korlát, addig a kis omegára ez nem mondható el. Tehát $\frac{n^2}{2} \in \omega(n)$, de $\frac{n^2}{2} \not \in \omega(n^2)$.

Tulajdonságok:

• $\Theta(g) = O(g) \cap \Omega(g)$
• $o(g) \subset O(g) \setminus \Omega(g)$
• $\omega(g) \subset \Omega(g) \setminus O(g)$
• ha $f \in O(g)$ és $g \in O(h)$, akkor $f \in O(h)$ (tranzitivitás)
• ha $f \in \Omega(g)$ és $g \in \Omega(h)$, akkor $f \in \Omega(h)$ (tranzitivitás)
• ha $f \in \Theta(g)$ és $g \in \Theta(h)$, akkor $f \in \Theta(h)$ (tranzitivitás)
• $f \in \Theta(g) \iff g \in \Theta(f)$ (szimmetria)
• $f \in O(g) \iff g \in \Omega(f)$ (felcserélt szimmetria)
• $f \in O(f)$ és $f \in \Omega(f)$ és $f \in \Theta(f)$ (reflexivitás)

Aszimptotikus függvények nagyságrendjére:

Arra, hogy egy függvény egy másikhoz képest nagy $n$ értékekre elhanyagolható, bevezetjük az aszimptotikusan kisebb fogalmát. \[ \phi \prec g \iff \lim_{n \to \infty} \frac{\phi(n)}{g(n)} = 0 \] Ilyenkor azt mondjuk, hogy $\phi$ aszimptotikusan kisebb, mint $g$.

$log(n!) \in \Theta(n \cdot log \space n)$

${log \space n} \prec \sqrt{n} \prec n \prec {n \cdot log \space n} \prec n^2 \prec {{n^2} log \space n} \prec n^3 \prec 2^n \prec n! \prec n^n$

Nevezetes nagyságrendek:

Példa különféle algoritmusok maximális műveletigényére:

• Verem vagy sor bármely művelete: $\Theta(1)$
• Logaritmikus keresés: $\Theta(log \space n)$
• Prímszámteszt: $\Theta(n^\frac{1}{2})$
• Lineáris keresés: $\Theta(n)$
• Kupacrendezés: $\Theta(n \cdot log \space n)$
• Shell rendezés: $\Theta(n^\frac{3}{2})$
• Buborékrendezés: $\Theta(n^2)$
• Mátrixszorzás: $\Theta(n^3)$
• Hanoi tornyai: $\Theta(2^n)$
• Utazóügynök probléma: $\Theta(n!)$