Čo je veľká notácia Omega?

Podobne ako veľká notácia O, aj veľká funkcia Omega (Ω) sa v informatike používa na opísanie výkonu alebo zložitosti algoritmu.

Ak je doba chodu Ω (f (n)), potom pre dostatočne veľkú n je doba chodu najmenej k⋅f (n) pre nejakú konštantu k. Tu je príklad, ako uvažovať o dobe behu Ω (f (n)):

Hovoríme, že doba behu je „veľká-Ω f (n).“ Pre asymptotické dolné hranice používame notáciu s veľkým Ω , pretože pri dostatočne veľkých vstupných veľkostiach obmedzuje rast doby behu zospodu.

Rozdiel medzi veľkým O a veľkým Ω

Rozdiel medzi notáciou Big O a notáciou Big Ω je v tom, že Big O sa používa na popísanie najhoršej doby chodu algoritmu. Ale veľká Ω notácia sa na druhej strane používa na opísanie najlepšej doby behu prípadu pre daný algoritmus.

Viac informácií:

• Zápis Big-Ω (Big-Omega)