Kaj je Big Omega Notation?

Podobno kot pri velikem zapisu O se v računalništvu za opis delovanja ali zapletenosti algoritma uporablja tudi velika funkcija Omega (Ω).

Če je čas delovanja Ω (f (n)), potem je za dovolj velik n čas delovanja vsaj k⋅f (n) za neko konstanto k. Evo, kako si omisliti čas delovanja, ki je Ω (f (n)):

Pravimo, da je čas delovanja "velik-Ω f (n)." Za asimptotične spodnje meje uporabljamo zapis velikega Ω , saj omejuje rast delovnega časa od spodaj za dovolj velike vhodne velikosti.

Razlika med velikim O in velikim Ω

Razlika med zapisom Big O in zapisom Big Ω je, da se Big O uporablja za opis najslabšega časa delovanja algoritma. Toda po drugi strani se zapis velikega Ω uporablja za opis najboljšega časa delovanja za dani algoritem.

Več informacij:

• Zapis Big-Ω (Big-Omega)