Jeg forstår matematisk $ f (n) \ i O (g (n)) $: $ f (n) $ ikke vokse raskere enn $ g (n) $. Mer formelt eksisterer $ \ c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
Tilsvarende betyr $ f (n) \ in \ Theta (g (n)) $ at $ f (n) $ vokser omtrent like raskt som $ g (n) $. dvs. $ f (n) \ i O (g (n)), \ Omega (g (n)) $.
Det jeg ikke får, er hvorfor folk bruker stor Oh i løpet av en algoritme? Skal vi ikke bruke store Theta. Når vi sier «Kjøretid» til en algoritme, refererer vi til worst case kjøretid dvs. $ T (n) = maks \ {ALG (x): | x | = n \} $.
Så, for eksempel: den verste tilfellet kjøretid for lineært søk på en inngang på størrelse $ n $ ($ n $ elementer og en målverdi) er $ \ Theta (n) $ og $ O (n) $, men $ \ Theta (n) $ gir mer informasjon. Så hvorfor bruker algoritmebøker $ O (n) $ og ikke $ \ Theta (n) $.
Kommentarer
- Ofte ' s fordi vi rett og slett ikke kan ' t få en stram big-theta bundet på en algoritmes kjøretid. Hvis en algoritme er tilstrekkelig komplisert, kan det hende at det beste vi kan gjøre er å si kjøretiden, si $ O (n ^ {n!}) $ Hvor det faktisk kan være $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Historiske årsaker.
- " Det jeg ikke gjør ' er ikke hvorfor folk bruker store Oh for en algoritmes kjøretid? Bør ' t vi bruker store Theta. " – Ja. Vent ikke, vi burde komme med enda mer presise uttalelser. Men hvis jeg må velge, ja, $ \ Theta $!
Svar
Jeg ser to grunner til at folk foretrekker Big Oh framfor Big Theta:
- Runtidskompleksiteten til en algoritme er ikke nødvendigvis definert som den verste tilfelle runtime-kompleksiteten. Du kan også bare se det som kjøretid på en vilkårlig forekomst av lengden $ n $. Hvis du for eksempel skriver at kjøretiden $ t (n) $ til en algoritme er i $ \ mathcal {O} (n ^ 2) $ betyr dette at uansett hvilken inngang av lengden $ n $ du velger, vil den alltid vokse asymptotisk tregere enn funksjonen $ c \ cdot n ^ 2 $ for noen konstante $ c $ – så vi kommer tydeligvis med en uttalelse om den verste tilfelle kjøretiden.
- Noen ganger når du analyserer kjøretiden kompleksiteten til en algoritme du ikke vet helt sikkert om den verste tilfelle kompleksiteten du gir er veldig tett. Ta for eksempel kjøretidskompleksiteten til matrisemultiplikasjon . Der er det fremdeles ikke klart om kjøretiden $ n ^ {2.3728639} $ virkelig er det verste tilfellet. Dermed er kjøretiden kjent for å være i $ \ mathcal {O} (n ^ {2.3728639}) $ mens den » er ikke sikker på om det er i $ \ Theta (n ^ {2.3728639}) $.
Men også, du har rett i at det i noen tilfeller ville være bedre å gi en Big Theta bundet enn en Big Oh-bundet.
Kommentarer
- Annonse 1: Lesere, vær forsiktig for ikke å lese for mye i det !
Svar
En (slurvet) øvre grense er lettere å bevise enn en stram øvre grense, enn si øvre og nedre grenser.
Noen algoritmers kjøretid kan «t gis med samme funksjon som øvre / nedre grense. F.eks. enkle sorteringsalgoritmer er $ O (n ^ 2) $, men har lavere grense $ \ Omega (n) $.
Noen insisterer på å forsøke å gi ytelse i asymptotiske termer via $ \ sim $, hvor $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(si som et gjennomsnitt, eller i verste fall, når det gjelder antall kritiske operasjoner, for eksempel sammenligninger ved sortering). Dvs. vrikkerom, men ingen (muligens humongøse) konstanter feide under teppet.
Kommentarer
- Når vi refererer til " kjøretid ", vi refererer til noe som best-case kjøretid, worst-case kjøretid og gjennomsnittlig case kjøretid. F.eks: Quicksort har $ \ Theta (n ^ 2) $ worst case kjøretid og $ \ Theta (n) $ best case kjøretid. Asymptotika er definert på funksjonene til høyre.
Svar
Hvis stor-Theta kan brukes i stedet for stor- Åh, den skal brukes med mindre den gir unødvendige vanskeligheter med å forstå. Det er noen subtile tilfeller når big-Theta ikke kan brukes i stedet for big-Oh, for eksempel:
Vurder følgende problem: sorter matriser med jevn lengde. Programmet for å løse dette problemet kan være: Hvis matriselengden er merkelig, kan du avslutte umiddelbart, hvis matriselengden til og med gjør boblesortering. Hva er den verste tilfelle kjøretiden til denne algoritmen?
Det er sikkert $ O (n ^ 2) $, men det er IKKE $ \ Omega (n ^ 2) $ i betydningen $ \ Omega $ defineres vanligvis. I stedet er den dårligste kjøretiden «$ \ Omega (n ^ 2) $ uendelig ofte» så å si (advarsel: ikke-standard terminologi).
Svar
I svaret på «hvorfor bruker algoritmebøker big-Oh og ikke Theta»:
Big-Oh brukes til worst case-analyse og Big-Omega brukes kun for best case. Men når vi analyserer med tanke på Big-Theta, snakker vi om både Big-Oh & Big-Omega samtidig.
dvs. For Big-Theta er det nødvendig at Big-Oh == Big-Omega, ellers kan vi ikke snakke om Big-Theta.
Så uansett hvor (bok / hvilket som helst dokument) du ser bruken av Big-Theta, de gir kompleksiteten til begge Big-Oh & Big-Omega (og begge er like også). Men i mange tilfeller er de ikke like da bruker vi bare Big- Å bare i verste fall.