Ik begrijp wiskundig $ f (n) \ in O (g (n)) $: $ f (n) $ niet sneller groeien dan $ g (n) $. Formeler gezien bestaat $ \ c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
Evenzo betekent $ f (n) \ in \ Theta (g (n)) $ dat $ f (n) $ ongeveer even snel groeit als $ g (n) $. dwz $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
Wat ik niet begrijp is waarom mensen grote Oh gebruiken voor de duur van een algoritme? Moeten we geen grote Theta gebruiken. Als we “Looptijd” van een algoritme zeggen, verwijzen we naar de looptijd in het slechtste geval, d.w.z. $ T (n) = max \ {ALG (x): | x | = n \} $.
Dus, ex: de slechtste looptijd van lineair zoeken op een invoer met de grootte $ n $ ($ n $ elementen en een doelwaarde) is $ \ Theta (n) $ en $ O (n) $, maar $ \ Theta (n) $ geeft meer informatie. Dus waarom gebruiken algoritmeboeken $ O (n) $ en niet $ \ Theta (n) $.
Reacties
- Vaak ‘ s omdat we ‘ gewoon geen strakke grote theta kunnen krijgen voor de looptijd van een algoritme. Als een algoritme voldoende gecompliceerd is, kan het gebeuren dat we het beste kunnen zeggen dat de looptijd bijvoorbeeld $ O (n ^ {n!}) $ Is, terwijl het in werkelijkheid $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Historische redenen.
- ” Wat ik don ‘ t snapt waarom mensen grote Oh gebruiken voor de looptijd van een algoritme? Moeten we niet ‘ t we grote Theta gebruiken. ” – Ja. Wacht, niet, we zouden nog nauwkeuriger uitspraken moeten doen. Maar als ik moet kiezen, ja, $ \ Theta $!
Antwoord
Ik zie twee redenen waarom mensen geven de voorkeur aan Big Oh boven Big Theta:
- De runtime-complexiteit van een algoritme is niet noodzakelijk gedefinieerd als de worst-case runtime-complexiteit. Je zou het ook gewoon kunnen zien als de runtime op een willekeurige instantie met de lengte $ n $. Als u dan bijvoorbeeld schrijft dat de runtime $ t (n) $ van een algoritme in $ \ mathcal {O} (n ^ 2) $ staat, betekent dit dat welke invoer van lengte $ n $ u ook kiest, deze altijd zal groeien asymptotisch langzamer dan de functie $ c \ cdot n ^ 2 $ voor een constante $ c $ – dus we doen dan duidelijk een uitspraak over de worst-case runtime.
- Soms als je de runtime analyseert complexiteit van een algoritme waarvan u niet zeker weet of de complexiteit in het slechtste geval die u geeft erg krap is. Neem bijvoorbeeld de runtime-complexiteit van matrixvermenigvuldiging . Daar is het nog steeds niet duidelijk of de runtime $ n ^ {2.3728639} $ echt het slechtste geval is. En dus is bekend dat de runtime in $ \ mathcal {O} (n ^ {2.3728639}) $ is terwijl het ” weet niet zeker of het in $ \ Theta (n ^ {2.3728639}) $ staat.
Maar je hebt ook gelijk dat het in sommige gevallen beter is om een Big Theta gebonden dan een Big Oh gebonden.
Opmerkingen
- Advertentie 1: Lezers, wees voorzichtig om daar niet te veel in te lezen !
Antwoord
Een (slordige) bovengrens is gemakkelijker te bewijzen dan een strakke bovengrens, laat staan bovengrenzen en ondergrenzen.
De looptijd van een algoritme kan “t worden gegeven met dezelfde functie als boven- / ondergrens. Bijv. eenvoudige sorteeralgoritmen zijn $ O (n ^ 2) $, maar hebben een ondergrens $ \ Omega (n) $.
Sommigen staan erop te streven naar asymptotische prestaties via $ \ sim $, waarbij $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(zeg maar als een gemiddelde, of in het slechtste geval, in termen van een aantal kritische bewerkingen, zoals vergelijkingen bij het sorteren). Dat wil zeggen, bewegingsruimte, maar er worden geen (mogelijk gigantische) constanten onder het tapijt geveegd.
Opmerkingen
- Wanneer we verwijzen naar ” looptijd “, we verwijzen naar zoiets als best-case looptijd, worst-case looptijd en gemiddelde looptijd. Bijv .: Quicksort heeft $ \ Theta (n ^ 2) $ looptijd in het slechtste geval en $ \ Theta (n) $ looptijd in het beste geval. Asymptotiek wordt gedefinieerd op functies rechts.
Antwoord
Als big-Theta kan worden gebruikt in plaats van big- Oh, het moet worden gebruikt, tenzij het onnodig moeilijk maakt om het te begrijpen. Er zijn enkele subtiele gevallen waarin big-Theta niet kan worden gebruikt in plaats van big-Oh, bijvoorbeeld:
Beschouw het volgende probleem: sorteer arrays van even lengte. Het programma om dit probleem op te lossen zou kunnen zijn: als de array-lengte oneven is, sluit dan onmiddellijk af, als de array-lengte even is, sorteer dan bellen. Wat is de slechtste looptijd van dit algoritme?
Het is zeker $ O (n ^ 2) $, maar het is NIET $ \ Omega (n ^ 2) $ in de zin $ \ Omega $ wordt gewoonlijk gedefinieerd. In plaats daarvan is de looptijd in het slechtste geval “$ \ Omega (n ^ 2) $ oneindig vaak” om zo te zeggen (waarschuwing: niet-standaard terminologie).
Antwoord
In het antwoord van “waarom gebruiken algoritmeboeken big-Oh en niet Theta”:
Big-Oh wordt gebruikt voor de analyse van het slechtste geval en Big-Omega wordt alleen voor het beste geval gebruikt. Maar als we in termen van Big-Theta analyseren, hebben we het over Big-Oh & Big-Omega tegelijkertijd.
dwz. Voor Big-Theta is het noodzakelijk dat Big-Oh == Big-Omega, anders kunnen we “niet praten over Big-Theta.
Dus waar ooit (boek / document) je het gebruik van ziet Big-Theta, ze geven de complexiteit van beide Big-Oh & Big-Omega (en beide zijn ook gelijk). Maar in veel gevallen zijn ze niet gelijk, dan gebruiken we alleen Big- Oh alleen in het ergste geval.