I denne veiledningen vil du lære hva asymptotiske notasjoner er. Du vil også lære om Big-O-notasjon, Theta-notasjon og Omega-notasjon.
Effektiviteten til en algoritme avhenger av hvor lang tid, lagring og andre ressurser som kreves for å utføre algoritmen. Effektiviteten måles ved hjelp av asymptotiske notasjoner.
En algoritme har kanskje ikke samme ytelse for forskjellige typer innganger. Med økningen i inngangsstørrelsen vil ytelsen endres.
Studien av endring i ytelsen til algoritmen med endringen i rekkefølgen på inngangsstørrelsen er definert som asymptotisk analyse.
Asymptotiske notasjoner
Asymptotiske notasjoner er de matematiske notasjonene som brukes til å beskrive kjøretid for en algoritme når inngangen har en tendens til en bestemt verdi eller en begrensningsverdi.
For eksempel: Når boblesorteringen allerede er sortert, er algoritmens tid lineær, dvs. i beste fall.
Men når inngangsoppsettet er i omvendt tilstand, tar algoritmen maksimal tid (kvadratisk) for å sortere elementene, dvs. i verste fall.
Når inngangsmatrisen verken er sortert eller i omvendt rekkefølge, tar det gjennomsnittlig tid. Disse varighetene er angitt med asymptotiske notasjoner.
Det er hovedsakelig tre asymptotiske notasjoner:
- Big-O-notasjon
- Omega-notasjon
- Theta notasjon
Big-O-notasjon (O-notasjon)
Big-O-notasjon representerer den øvre grensen for en algoritmes kjøretid. Dermed gir det den verste tilfelle kompleksiteten til en algoritme.
Big-O gir øvre grense for en funksjon
O (g (n)) = (f (n): det eksisterer positive konstanter c og n 0 slik at 0 ≦ f (n) ≦ cg (n) for alle n ≧ n 0 )
Ovennevnte uttrykk kan beskrives som en funksjon f(n)tilhører settet O(g(n))hvis det eksisterer en positiv konstant cslik at den ligger mellom 0og cg(n)for tilstrekkelig stor n.
For en verdi av nkrysser ikke en algoritmes tid som tilbys av O(g(n)).
Siden det gir worst-case kjøretid for en algoritme, brukes den mye til å analysere en algoritme, ettersom vi alltid er interessert i worst-case scenariet.
Omega-notasjon (Ω-notasjon)
Omega-notasjon representerer den nedre grensen for en algoritmes kjøretid. Dermed gir det best mulig kompleksitet av en algoritme.
Omega gir den nedre grensen for en funksjon
Ω (g (n)) = (f (n): det eksisterer positive konstanter c og n 0 slik at 0 ≦ cg (n) ≦ f (n) for alle n ≧ n 0 )
Ovennevnte uttrykk kan beskrives som en funksjon f(n)tilhører settet Ω(g(n))hvis det eksisterer en positiv konstant cslik at den ligger over cg(n), for tilstrekkelig stor n.
For hvilken som helst verdi av ner minimumstiden som kreves av algoritmen gitt av Omega Ω(g(n)).
Theta Notasjon (Θ-notasjon)
Theta-notasjonen omslutter funksjonen ovenfra og nedenfra. Siden den representerer øvre og nedre grense for en algoritmes kjøretid, brukes den til å analysere den gjennomsnittlige sakskompleksiteten til en algoritme.
Theta avgrenser funksjonen innenfor konstantfaktorer
For en funksjon g(n), Θ(g(n))er gitt av forholdet:
Θ (g (n)) = (f (n): det eksisterer positive konstanter c 1 , c 2 og n 0 slik at 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) for alle n ≧ n 0 )
Ovennevnte uttrykk kan beskrives som en funksjon f(n)tilhører settet Θ(g(n))hvis det eksisterer positive konstanter og slik at det kan være klemt mellom og for tilstrekkelig stor n.c1c2c1g(n)c2g(n)
Hvis en funksjon f(n)ligger hvor som helst i mellom og for alle , sies det å være asymptotisk tett bundet.c1g(n)c2g(n)n ≧ n0f(n)
