Asymptotisk notasjon og beste/verste tilfelle
Jeg er litt forvirret. Jeg trodde \(\Theta\) var worst-case kjøretid, men boken bruker plutselig \(O\). I tillegg bruker den \(\Theta\) for average kjøretid. Var ikke \(O\) gjennomsnittlig kjøretid? Og \(\Theta\) worst-case? I tillegg sier boken at noe krever minne \(\Theta(n)\); hvorfor bruker de \(\Theta\) for minne også?
Her blander du sammen to helt separate begreper. Best-/worst-/average-case har ingenting med \(O\)/\(\Omega\)/\(\Theta\) å gjøre i seg selv. Det er noen sammenhenger i hvordan vi ofte bruker dem, men definisjonene er separate. Og \(O\)/\(\Omega\)/\(\Theta\) har heller ingenting med tid å gjøre – man kan godt bruke det om minnebruk eller avstand, for den saks skyld, om man skulle ønske det.
Jeg anbefaler at du først prøver å skjønne definisjonene av begrepene ordentlig (f.eks. slå opp i indeksen på \(\Theta\) og let videre derfra), og også definisjonen av worst-case, etc., og sørg for at fundamentet er solid før du går videre. Men her er en kjapp oppsummering.
Best-/worst-/average-case
Vi beskriver ofte ressursbruken til en algoritme – f.eks. hvor mange operasjoner den utfører (kjøretid) eller hvor mye minne den bruker – som en funksjon av størrelsen på input, problemstørrelsen (egentlig størrelsen på en problem-instans). Så vi kan f.eks. skrive \(T(n)\) for kjøretiden, der \(n\) er størrelsen på input. Hvis algoritmen har samme kjøretid uansett hva slags input vi har, så er jo dette helt greit, men det er ikke alltid tilfelle. F.eks. tar Insertion-Sort kvadratisk tid for noen inputs og lineær tid for andre.
Her kan vi f.eks. si at best-case-kjøretiden \(T_{\textrm{best}}(n)\) er minimum av kjøretiden for alle instanser av størrelse \(n\). Worst-case vil være maksimum, mens average er gjennomsnitt. Gjennomsnittet kan f.eks. tas over alle gyldige inputs, eller vi kan ha et vektet gjennomsnitt basert på en sannsynlighetsfordeling (forventningsverdi).
Men: Dette har altså ingenting direkte med asymptotisk notasjon å gjøre. Det er bare snakk om å beskrive kjøretiden for ulike typer inputs. Vi kan godt gi en eksakt funksjon for antall operasjoner, f.eks. La oss ta Insertion-Sort. Hvis vi måler kjøretiden i antall sammenligninger har den \(T_{\textrm{best}}(n) = n-1\) og \(T_{\textrm{worst}}(n) = n(n-1)/2\). Dette er begge deler helt eksakte funksjoner for hvor mange sammenligninger vi må utføre i beste og verste tilfelle. Det er ingen asymptotisk notasjon inne i bildet.
Asymptotisk notasjon
Hvis vi ikke vil skille mellom antall sammenligninger og antall sekunder, eller vi har diverse andre smådetaljer vi vil se bort fra, så kan vi bruke asymptotisk notasjon. De asymptotiske operatorene våre definerer mengder med funksjoner, så f.eks. \(O(n^2)\) er mengden av alle funksjoner som for store nok \(n\) er proporsjonale med noe som er mindre eller lik \(n^2\). Det vil si at for Insertion-Sort er både \(T_{\textrm{best}}\) og \(T_{\textrm{worst}}\) i denne mengden. Bare \(T_{\textrm{best}}\) er i mengden \(O(n)\).
Motsatt, så er \(\Omega(n^2)\) mengden av alle funksjoner som for store nok \(n\) er proporsjonale med noe som er større eller lik \(n^2\). Det gjelder bare \(T_{\textrm{worst}}\), mens begge funksjonene er i mengden \(\Omega(n)\).
Og så har vi \(\Theta\), som bare er snittet av de andre to. Det vil si, \(\Theta(n^2)\) er mengden funksjoner som for store nok \(n\) er proporsjonale med én funksjon som er større eller lik \(n^2\) og én funksjon som er mindre eller lik \(n^2\). Av de to vi har sett på gjelder det bare \(T_{\textrm{worst}}\). Til gjengjeld er det bare \(T_{\textrm{best}}\) som er i mengden \(\Theta(n)\).
Hva er sammenhengen?
Kort fortalt gir altså \(O\) en asymptotisk øvre grense, \(\Omega\) gir en nedre grense, og \(\Theta\) gir både en øvre og en nedre grense samtidig, og er altså mer presis enn de andre to. Hva har dette generelt med best-/worst-/average-case å gjøre? Egentlig ingenting. Alle tre funksjonene kan beskrives av alle de tre asymptotiske operatorene. Men vi kan se noen sammenhenger likevel.
Poenget er at om vi ikke spesifiserer om vi snakker om best-, average- eller worst-case, så må vi ta høyde for alle. Dvs., vi må bruke en asymptotisk operator som gir oss en mengde som inneholder både best-case og worst-case. Det gjelder når vi sier at «Algoritme X har kjøretid Y», uten å si noe spesielt om hva slags input det gjelder (best/worst).
Dersom best-case og worst-case har forskjellig asymptotisk kjøretid kan vi da ikke bruke \(\Theta\), for eksempel, siden den aldri vil kunne favne både best-case og worst-case. Vi kan ikke si at Insertion-Sort har kjøretid \(\Theta(f(n))\) for noen \(f\). Det går ikke. Vi kan si at den har kjøretid \(O(n^2)\) og vi kan si at den har kjøretid \(\Omega(n)\), siden begge disse mengdene favner både best- og worst-case. Og det er her forvirringen ofte kommer inn (selv om det ser ut til at du har byttet litt om på rollen til \(O\) og \(\Theta\) i den klassiske forvirringen).
For når vi beskriver algoritmer slik, så vil vi jo gjerne ende opp med å bruke \(O\) til å beskrive worst-case og \(\Omega\) til å beskrive best-case. Men det er altså bare fordi vi vil favne begge to!
Tenk på det jeg såvidt har vært innom (og som vi skal se nærmere på siden), om at det ikke går an å få noe bedre kjøretid enn \(\Omega(n\lg n)\) for sortering. Vi vet jo allerede (fra Insertion-Sort) at det ikke er sant for best-case – dette utsagnet gjelder kun worst-case. Men det er samtidig snakk om en nedre grense.
Med andre ord: For generell sammenligningsbasert sortering er worst-case-kjøretiden \(\Omega(n\lg n)\).
Altså: Man kan fint bruke \(\Omega\) om worst-case. For eksempel. Alle tre operatorer kan brukes om alle tre tilfeller, så lenge vi spesifiserer hva vi snakker om.
Og, ja, vi kan også bruke dem til å beskrive andre funksjoner. De er bare operatorer som gir oss mengder med funksjoner, og det spiller ingen rolle om mengdene beskriver kjøretid eller minnebruk, f.eks.
Håper det hjalp litt!