Az Ω (Omega) jelölés

Néha csak annyit akarunk mondani, hogy egy algoritmus legalább adott idő alatt fut le, anélkül, hogy felső határt is megadunk. Ekkor az Ω jelölést használjuk. Ez a görög „omega” betű.

Ha a futási idő $\mathrm{\Omega }(f(n))$‍, akkor elég nagy $n$‍ esetén a futási idő minimum $k\cdot f(n)$‍ valamilyen konstans $k$‍ érték mellett. Az $\mathrm{\Omega }(f(n))$‍ futási időt így kell elképzelni:

Azt mondjuk, a futási idő „$f(n)$‍ omegája”. Az Ω jelölést aszimptotikus alsó korlátként használjuk, mivel a futási időt alulról korlátozza, ha az input mérete elég nagy.

Ahogyan a $\mathrm{\Theta }(f(n))$‍ automatikusan megadja $O(f(n))$‍-t, úgy automatikusan megadja $\mathrm{\Omega }(f(n))$‍-t is. Tehát mondhatjuk azt, hogy a bináris keresés futási ideje a legrosszabb esetben $\mathrm{\Omega }({\log }_{2}n)$‍.

Helyes, bár pontatlan kijelentést tehetünk Ω jelölés használatakor is. Például ha tényleg egymillió dollár van a zsebedben, akkor az igazságnak megfelelően mondhatod, hogy „van egy bizonyos pénzösszeg a zsebemben, és az legalább 10 dollárnyit tesz ki”. Ez igaz, de egyáltalán nem pontos. Ehhez hasonlóan az igazságnak megfelelően, bár nem túl pontosan állíthatjuk azt, hogy a bináris keresés futási ideje a legrosszabb esetben $\mathrm{\Omega }(1)$‍, mert tudjuk, hogy legalább konstans időt vesz igénybe.

Persze általában, amikor algoritmusokról beszélünk, akkor a futási időt lehetőleg pontosan szeretnénk meghatározni. Itt azért mutattunk pontatlan állításokat, hogy jobban megértsed az $\mathrm{\Omega }$‍, $O$‍ és $\mathrm{\Theta }$‍ jelöléseket.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.