Jeg forstår matematisk $ f (n) \ i O (g (n)) $: $ f (n) $ ikke vokse hurtigere end $ g (n) $. Mere formelt findes $ \ c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
På samme måde betyder $ f (n) \ in \ Theta (g (n)) $, at $ f (n) $ vokser omtrent så hurtigt som $ g (n) $. dvs. $ f (n) \ i O (g (n)), \ Omega (g (n)) $.
Hvad jeg ikke får, er, hvorfor folk bruger stor Oh i løbetid en algoritme? Skal vi ikke bruge store Theta. Når vi siger “Running time” for en algoritme, henviser vi til worst case-kørselstid, dvs. $ T (n) = max \ {ALG (x): | x | = n \} $.
Så f.eks. er den værste tilfælde kørselstid for lineær søgning på et input med størrelsen $ n $ ($ n $ -elementer og en målværdi) er $ \ Theta (n) $ og $ O (n) $, men $ \ Theta (n) $ giver mere information. Så hvorfor bruger algoritmebøger $ O (n) $ og ikke $ \ Theta (n) $.
Kommentarer
- Ofte ' s, fordi vi simpelthen ikke kan ' t få en stram big-theta bundet af en algoritmes driftstid. Hvis en algoritme er tilstrækkelig kompliceret, kan det ske, at det bedste, vi kan gøre, er at sige, at køretiden er, siger $ O (n ^ {n!}) $, Hvor det faktisk kan være $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Historiske grunde.
- " Hvad jeg ikke ' er det ikke, hvorfor folk bruger stor Oh til en algoritmes driftstid? Bør ' t bruger vi stor Theta. " – Ja. Vent ikke, vi skal komme med endnu mere præcise udsagn. Men hvis jeg skal vælge, ja, $ \ Theta $!
Svar
Jeg ser to grunde til folk foretrækker Big Oh frem for Big Theta:
- En algoritmes runtime-kompleksitet er ikke nødvendigvis defineret som den værste-case-runtime-kompleksitet. Du kan muligvis bare se det som runtime på en vilkårlig forekomst af længden $ n $. Hvis du f.eks. Skriver, at runtime $ t (n) $ for en algoritme er i $ \ mathcal {O} (n ^ 2) $ betyder det, at uanset hvilken inputlængde $ n $ du vælger, vil den altid vokse asymptotisk langsommere end funktionen $ c \ cdot n ^ 2 $ for nogle konstante $ c $ – så vi kommer så tydeligvis med en erklæring om den værste tilfælde runtime.
- Nogle gange når du analyserer runtime kompleksiteten af en algoritme, som du ikke ved helt sikkert, om den værst tænkelige kompleksitet, du giver, er virkelig stram. Tag f.eks. runtime-kompleksiteten af matrixmultiplikation . Der er det stadig ikke klart, om runtime $ n ^ {2.3728639} $ virkelig er det værste tilfælde. Og det er således kendt, at runtime er i $ \ mathcal {O} (n ^ {2.3728639}) $, mens det ” er ikke sikker på, om det er i $ \ Theta (n ^ {2.3728639}) $.
Men også, du har ret i, at det i nogle tilfælde ville være bedre at give en Big Theta bundet end en Big Oh-bundet.
Kommentarer
- Annonce 1: Læsere, pas på for ikke at læse for meget i det !
Svar
En (sjusket) øvre grænse er lettere at bevise end en tæt øvre grænse, endsige øvre og nedre grænser.
Nogle algoritmers kørselstid kan “t gives med samme funktion som øvre / nedre grænse. For eksempel. enkle sorteringsalgoritmer er $ O (n ^ 2) $, men har lavere grænser $ \ Omega (n) $.
Nogle insisterer på at stræbe efter at give ydeevne i asymptotiske termer via $ \ sim $, hvor $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(sig som et gennemsnit eller i værste fald i antal af en eller anden kritisk operation, såsom sammenligninger ved sortering). Det vil sige, wiggle room, men ingen (muligvis humongøse) konstanter fejet under tæppet.
Kommentarer
- Når vi henviser til " runtime ", vi henviser til noget som kørselstid i bedste tilfælde, kørselstid i værste tilfælde og kørselstid i gennemsnit. F.eks .: Quicksort har $ \ Theta (n ^ 2) $ worst case-driftstid og $ \ Theta (n) $ best case-driftstid. Asymptotics er defineret på højre funktion.
Svar
Hvis big-Theta kan bruges i stedet for big- Åh, det skal bruges, medmindre det tilføjer unødvendige vanskeligheder med at forstå. Der er nogle subtile tilfælde, hvor big-Theta ikke kan bruges i stedet for big-oh, fx:
Overvej følgende problem: Sorter arrays med lige længde. Programmet til at løse dette problem kan være: Hvis array længde er ulige exit straks, hvis array længde er endda gøre boble sortering. Hvad er den dårligste kørselstid for denne algoritme?
Det er helt sikkert $ O (n ^ 2) $, men det er IKKE $ \ Omega (n ^ 2) $ i den forstand $ \ Omega $ defineres normalt. I stedet er den værst tænkelige driftstid “$ \ Omega (n ^ 2) $ uendeligt ofte” så at sige (advarsel: ikke-standard terminologi).
Svar
I svaret “hvorfor bruger algoritmebøger big-Oh og ikke Theta”:
Big-Oh bruges til worst case-analysen, og Big-Omega bruges kun til bedste case. Men når vi analyserer med hensyn til Big-Theta, taler vi om både Big-Oh & Big-Omega samtidigt.
dvs. For Big-Theta er det nødvendigt, at Big-Oh == Big-Omega, ellers kan vi ikke tale om Big-Theta.
Så hvor som helst (bog / ethvert dokument) ser du brugen af Big-Theta, de giver kompleksiteten af begge Big-Oh & Big-Omega (og begge er også lige). Men i mange tilfælde er de ikke lige så bruger vi kun Big- Åh bare i værste fald.