Kas yra „Big Omega“ žymėjimas?

Panašiai kaip didelis „O“ žymėjimas, informatikos moksle naudojama didelė „Omega“ (Ω) funkcija, apibūdinanti algoritmo našumą ar sudėtingumą.

Jei veikimo laikas yra Ω (f (n)), tai pakankamai dideliam n nubėgimo laikas yra mažiausiai k⋅f (n) tam tikrai konstantai k. Štai kaip galvoti apie bėgimo laiką, kuris yra Ω (f (n)):

big-omega funkcija

Mes sakome, kad veikimo laikas yra „f-n (big-Ω)“. Asimptotinėms apatinėms riboms naudojame didįjį Ω žymėjimą , nes jis pakankamai riboja įvesties trukmės augimą iš apačios.

Skirtumas tarp didžiojo O ir didžiojo Ω

Skirtumas tarp „Big O“ žymėjimo ir „Big Ω“ žymėjimo yra tas, kad „Big O“ naudojamas apibūdinant algoritmo blogiausią atvejį. Kita vertus, „Big Ω“ žymėjimas naudojamas apibūdinant geriausio konkretaus algoritmo veikimo laiką.

Daugiau informacijos:

  • „Big-Ω“ („Big-Omega“) žymėjimas
MYCODSCHOOL Laiko sudėtingumo analizė