A nagy O jelöléshez hasonlóan a számítástechnikában a nagy Omega (Ω) függvényt használják egy algoritmus teljesítményének vagy összetettségének leírására.
Ha a futási idő Ω (f (n)), akkor elég nagy n esetén a futási idő legalább k⋅f (n) valamilyen állandó k esetén. Így gondolhatunk egy futási időre, amely Ω (f (n)):
Azt mondjuk, hogy a futási idő „f (n) nagy-Ω”. A nagy-Ω jelölést használjuk az aszimptotikus alsó határokhoz , mivel elég nagy bemeneti méret esetén ez alulról korlátozza a futási idő növekedését.
Különbség a nagy O és a nagy Ω között
A Big O jelölés és a Big Ω jelölés közötti különbség az, hogy Big O-t használnak az algoritmus legrosszabb futási idejének leírására. De a Big Ω jelölést használjuk az adott algoritmus legjobb futási idejének leírására.
Több információ:
- Big-Ω (Big-Omega) jelölés
