Mikä on iso omega-notaatio?

Samoin kuin iso O-notaatio, informaatiotieteessä käytetään isoa Omega (Ω) -funktiota kuvaamaan algoritmin suorituskykyä tai monimutkaisuutta.

Jos käyntiaika on Ω (f (n)), niin riittävän suurelle n: lle käyntiaika on ainakin k⋅f (n) jollekin vakiolle k. Näin ajatellaan ajoaikaa, joka on Ω (f (n)):

iso-omega-toiminto

Sanomme, että käyntiaika on ”f-n: n iso-Ω”. Käytämme iso-Ω-merkintää asymptoottisille alemmille rajoille , koska se rajoittaa ajoajan kasvua alhaalta riittävän suurille syöttökokoille.

Ero Big O: n ja Big Ω: n välillä

Ero Big O -merkinnän ja Big Ω -merkinnän välillä on se, että Big O: ta käytetään kuvaamaan algoritmin pahinta tapausta. Mutta toisaalta Big Ω -merkintää käytetään kuvaamaan tietyn algoritmin parhaita tapauksia.

Lisää tietoa:

  • Big-Ω (Big-Omega) -merkintä
MYCODSCHOOL Ajan monimutkaisuusanalyysi