Jag förstår matematiskt $ f (n) \ i O (g (n)) $: $ f (n) $ inte växa snabbare än $ g (n) $. Mer formellt finns $ \ c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
På samma sätt betyder $ f (n) \ in \ Theta (g (n)) $ att $ f (n) $ växer ungefär lika snabbt som $ g (n) $. dvs $ f (n) \ i O (g (n)), \ Omega (g (n)) $.
Vad jag inte får är varför människor använder stor Oh för körtiden för en algoritm? Ska vi inte använda stora Theta. När vi säger ”Running time” för en algoritm hänvisar vi till värsta fallets körtid, dvs $ T (n) = max \ {ALG (x): | x | = n \} $.
Så, ex: den värsta fallets körtid för linjär sökning på en ingång med storleken $ n $ ($ n $ element och ett målvärde) är $ \ Theta (n) $ och $ O (n) $, men $ \ Theta (n) $ ger mer information. Så varför använder algoritmböcker $ O (n) $ och inte $ \ Theta (n) $.
Kommentarer
- Ofta ' s eftersom vi helt enkelt inte kan ' t få en tät stor-theta-bunden på en algoritmes körtid. Om en algoritm är tillräckligt komplicerad kan det hända att det bästa vi kan göra är att säga körtiden är, säg $ O (n ^ {n!}) $ Där det faktiskt kan vara $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Historiska skäl.
- " Vad jag inte ' är inte varför människor använder stora Oh för en algoritmes gångtid? Bör ' t använder vi stor Theta. " – Ja. Vänta, inte, vi borde göra ännu mer exakta uttalanden. Men om jag måste välja, ja, $ \ Theta $!
Svar
Jag ser två skäl till varför människor föredrar Big Oh framför Big Theta:
- En algoritms körningskomplexitet definieras inte nödvändigtvis som den sämsta runtime-komplexiteten. Du kan också bara se det som körtid på en godtycklig förekomst av längden $ n $. Om du till exempel skriver att runtime $ t (n) $ för en algoritm är i $ \ mathcal {O} (n ^ 2) $ betyder det att oavsett vilken ingång av längden $ n $ du väljer kommer den alltid att växa asymptotiskt långsammare än funktionen $ c \ cdot n ^ 2 $ för någon konstant $ c $ – så vi gör då uppenbarligen ett uttalande om värsta fallets körtid.
- Ibland när du analyserar körtiden komplexiteten hos en algoritm som du inte vet säkert om den värsta fallkomplexiteten du ger är riktigt snäv. Ta till exempel runtime-komplexiteten för matrixmultiplikation . Där är det fortfarande inte klart om runtime $ n ^ {2.3728639} $ verkligen är det värsta fallet. Och därmed är runtime känd för att vara i $ \ mathcal {O} (n ^ {2.3728639}) $ medan den ” är inte säker på om den finns i $ \ Theta (n ^ {2.3728639}) $.
Men du har också rätt i att det i vissa fall skulle vara bättre att tillhandahålla en Big Theta bunden än en Big Oh-bunden.
Kommentarer
- Annons 1: Läsare, var försiktig att inte läsa för mycket i det !
Svar
En (slarvig) övre gräns är lättare att bevisa än en stram övre gräns, än mindre övre och nedre gränser.
Vissa algoritmers körtid kan ”t ges med samma funktion som övre / nedre gräns. T.ex. enkla sorteringsalgoritmer är $ O (n ^ 2) $, men har lägre gräns $ \ Omega (n) $.
Vissa insisterar på att sträva efter att ge prestanda i asymptotiska termer via $ \ sim $, där $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(säg som ett genomsnitt eller i värsta fall, i termer av antal kritiska operationer, till exempel jämförelser vid sortering). Det vill säga, vackla i rummet, men inga (eventuellt humongösa) konstanter svepte under mattan. ”>
runtime ", vi hänvisar till något som bästa möjliga körtid, sämsta körtid och genomsnittlig körtid. Exempel: Quicksort har $ \ Theta (n ^ 2) $ worst case-driftstid och $ \ Theta (n) $ bästa falltid. Asymptotik definieras på funktioner till höger.
Svar
Om stor-Theta kan användas istället för stor- Åh, det ska användas om det inte ger onödiga svårigheter att förstå. Det finns några subtila fall när big-Theta inte kan användas i stället för big-Oh, t.ex.:
Tänk på följande problem: sortera matriser med jämn längd. Programmet för att lösa detta problem kan vara: om matrislängden är udda går omedelbart ut, om matrislängden till och med gör bubblasortering. Vad är den sämsta körtiden för denna algoritm?
Det är säkert $ O (n ^ 2) $, men det är INTE $ \ Omega (n ^ 2) $ i betydelsen $ \ Omega $ definieras vanligtvis. I stället är dess värsta fall ”$ \ Omega (n ^ 2) $ oändligt ofta” så att säga (varning: icke-standardterminologi).
Svar
I svaret ”varför använder algoritmböcker big-Oh och inte Theta”:
Big-Oh används för värsta fall-analysen och Big-Omega används endast för bästa fall. Men när vi analyserar i termer av Big-Theta, pratar vi om både Big-Oh & Big-Omega samtidigt.
dvs. För Big-Theta är det nödvändigt att Big-Oh == Big-Omega, annars kan vi inte prata om Big-Theta.
Så var som helst (bok / valfritt dokument) ser du användningen av Big-Theta, de ger komplexiteten i båda Big-Oh & Big-Omega (och båda är lika lika). Men i många fall är de inte lika då använder vi bara Big- Åh bara i värsta fall.