Nagy ordó jelölés

A nagy ordó jelölés egy olyan, matematikában használt jelölésmód, amely tömören fejezi ki egy adott függvény növekedésének mértékét. Informatikában általában egy algoritmus futásidejének jellemzésére használjuk: a vizsgált függvény a futáshoz szükséges időt adja meg a bemenet hosszának függvényében. Leegyszerűsítve, egy O(n^2) futásidejű algoritmus kétszer akkora méretű bemenetre négyszer annyi ideig fog futni, háromszor akkora bemenetre kilencszer annyi ideig. Míg maga a futásidőt leíró függvény függ az implementáció részleteitől és a futtatáshoz használt architektúrától, az algoritmus nagy ordója csak az algoritmus alapelvétől függ.

Definíció

Legyenek f(x) és g(x) egyváltozós függvények. Azt mondjuk, hogy f(x) = O(g(x)) (kiejtése: f(x) egyenlő nagy ordó g(x)) akkor és csak akkor, ha léteznek olyan M és x0 pozitív számok, hogy minden x>x0 esetén abs(f(x)) <= M*abs(g(x)).

Ugyanezt intuitívan átfogalmazva: f(x) = O(g(x)), ha elegendően nagy x esetén g(x) csak konstansszor több, mint f(x), azaz f(x) "nem nő gyorsabban" g(x)-nél.

Levezetése

Bár egy függvény nagy ordója levezethető tisztán elméleti alapon, a gyakorlatban két egyszerű szabály követésével is megkapható:

1. Egy összegből mindig a leggyorsabban növekedő tagot tartjuk meg. (Polinomok esetén ez a legnagyobb kitevőjű tag.)
2. A szorzatokból eltávolítjuk a konstans tagokat (amik értéke nem függ a változótól).

Például a 12x^3 + 2x^2 + 3 kifejezésből az első szabály alapján ezt kapjuk: 12x^3 majd alkalmazva a második szabályt: x^3

Vagyis 12x^3 + 2x^2 + 3 = O(x^3)

A fenti szabályokból következik, hogy logaritmus esetén nem lényeges a logaritmus alapja, hiszen a különböző alapú logaritmusok között egy konstans szorzóval lehetséges az átváltás.

Tulajdonságai

Bár az egyenlőségjel alapján azt gondolhatnánk, hogy egy függvény nagy ordója egyértelmű, a definíció több nagy ordót is megenged. Például az f(x) = 12x+1 függvény esetén f(x)=O(x) és f(x)=O(x^2) egyaránt igaz a definíció szerint. A gyakorlatban mindig a legkisebb lehetséges nagy ordót adjuk meg, ami viszont már egyértelmű.

A nagy ordó korlátlanul növekedő változó esetén jellemzi a függvényt, kis változóértékekre kevés információt hordoz. Könnyen lehetséges például, hogy egy O(x^2) függvény kisebb egy O(x) függvénynél a gyakorlatban előforduló x-ekre, mert az O(x) függvény nagy konstans szorzókat tartalmaz. Ezért fontos, hogy ha egy feladathoz algoritmust választunk, ne kizárólag a nagy ordós futásidőt vegyük figyelembe, hanem a konkrét adatokra várható futásidőt is.