Što je velika Omega notacija?

Slično velikom O zapisu, i velika Omega (Ω) funkcija koristi se u računalnim znanostima za opisivanje izvedbe ili složenosti algoritma.

Ako je vrijeme rada Ω (f (n)), tada je za dovoljno veliko n vrijeme izvođenja najmanje k⋅f (n) za neku konstantu k. Evo kako zamisliti vrijeme izvođenja koje je Ω (f (n)):

big-omega funkcija

Kažemo da je vrijeme izvođenja "veliko-Ω od f (n)." Oznaku velikog Ω koristimo za asimptotske donje granice , jer ograničava rast radnog vremena odozdo za dovoljno velike ulazne veličine.

Razlika između Velikog O i Velikog Ω

Razlika između oznake Big O i oznake Big Ω je u tome što se Big O koristi za opis najgoreg vremena rada algoritma. No, s druge strane, oznaka Velikog Ω koristi se za opis najboljeg vremena izvođenja za dati algoritam.

Više informacija:

  • Oznaka Big-Ω (Big-Omega)
MYCODSCHOOL Analiza složenosti vremena