Matematicky chápu $ f (n) \ v O (g (n)) $: $ f (n) $ ne rostou rychleji než $ g (n) $. Více formálně, $ \ existuje c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
Podobně $ f (n) \ in \ Theta (g (n)) $ znamená, že $ f (n) $ roste přibližně stejně rychle jako $ g (n) $. tj. $ f (n) \ v O (g (n)), \ Omega (g (n)) $.
To, co nezískám, je důvod, proč lidé používají velký Oh pro dobu běhu algoritmus? Neměli bychom používat velkou Thetu. Když řekneme „doba chodu“ algoritmu, máme na mysli nejhorší dobu chodu, tj. $ T (n) = max \ {ALG (x): | x | = n \} $.
Takže například: nejhorší doba běhu lineárního vyhledávání na vstupu o velikosti $ n $ (prvky $ n $ a cílová hodnota) je $ \ Theta (n) $ a $ O (n) $, ale $ \ Theta (n) $ poskytuje více informací. Proč tedy knihy s algoritmy používají $ O (n) $ a ne $ \ Theta (n) $.
Komentáře
- Často ' s, protože jednoduše nemůžeme ' získat pevně vázanou big-theta dobu běhu algoritmu. Pokud je algoritmus dostatečně komplikovaný, mohlo by se stát, že to nejlepší, co můžeme udělat, je říct, že doba běhu je, řekněme $ O (n ^ {n!}) $, Kde ve skutečnosti může být $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Historické důvody.
- " Co ne ' Je to důvod, proč lidé používají velký čas pro dobu chodu algoritmu? Neměli bychom ' t používat velkou Thetu. " – Ano. Počkejte, ne, měli bychom učinit ještě přesnější prohlášení. Pokud si ale musím vybrat, ano, $ \ Theta $!
Odpovědět
Vidím dva důvody, proč lidé upřednostňují Big Oh před Big Theta:
- Runtime složitost algoritmu není nutně definována jako nejhorší runtime složitost. Můžete to také vidět jako runtime na libovolné instanci délky $ n $. Pokud například napíšete, že runtime algoritmu $ t (n) $ je v $ \ mathcal {O} (n ^ 2) $, znamená to, že jakýkoli vstup délky $ n $, který si vyberete, bude vždy růst asymptoticky pomalejší než funkce $ c \ cdot n ^ 2 $ pro nějakou konstantu $ c $ – takže očividně uděláme prohlášení o nejhorší době běhu.
- Někdy při analýze doby běhu složitost algoritmu, o kterém nevíte, jestli nejhorší složitost, kterou dáváte, je opravdu malá. Vezměte si například běhovou složitost maticového násobení . Tam stále není jasné, zda je runtime $ n ^ {2.3728639} $ opravdu ten nejhorší případ. Je tedy známo, že runtime je v $ \ mathcal {O} (n ^ {2.3728639}) $, zatímco to “ nejste si jisti, zda je v $ \ Theta (n ^ {2.3728639}) $.
Máte ale také pravdu, že v některých případech by bylo lepší poskytnout velkou Thetu vázán než vázán Big Oh.
Komentáře
- Reklama 1: Čtenáři, buďte opatrní do toho moc nečíst !
odpověď
(Nedbalá) horní hranice je snazší prokázat než těsná horní hranice, natož horní a dolní hranice.
Některé algoritmy „runtime can“ t mají stejnou funkci jako horní / dolní mez. Např. jednoduché třídicí algoritmy jsou $ O (n ^ 2) $, ale mají dolní mez $ \ Omega (n) $.
Někteří trvají na tom, že se budou snažit poskytovat výkon asymptoticky pomocí $ \ sim $, kde $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(řekněme jako průměrný nebo nejhorší případ z hlediska počtu některých kritických operací, například srovnání při třídění). Tj. Kroutit místností, ale žádné (možná humongní) konstanty nespadly pod koberec.
Komentáře
- Když mluvíme o " runtime " označujeme něco jako běh v nejlepším případě, nejhorší běh a průměrný běh. Např .: Quicksort má $ \ Theta (n ^ 2) $ nejhorší dobu běhu a $ \ Theta (n) $ nejlepší dobu běhu. Asymptotika jsou definována na pravých funkcích.
Odpověď
Pokud lze místo big- Theta použít big-Theta Mělo by se použít, pokud to nepřináší zbytečné potíže s porozuměním. Existuje několik drobných případů, kdy big-Theta nelze použít místo big-Oh, například:
Zvažte následující problém: třídění polí sudé délky. Program k vyřešení tohoto problému může být: pokud je délka pole lichá, okamžitě ukončete, pokud je délka pole sudá, proveďte třídění bublin. Jaká je nejhorší doba běhu tohoto algoritmu?
Je to určitě $ O (n ^ 2) $, ale NENÍ to $ \ Omega (n ^ 2) $ ve smyslu $ \ Omega $ je obvykle definována. Místo toho je nejhorší doba běhu takříkajíc „$ \ Omega (n ^ 2) $ nekonečně často“ (varování: nestandardní terminologie).
Odpověď
V odpovědi „proč knihy s algoritmy používají big-oh a ne Theta“:
Big-Oh se používá pro analýzu nejhorších případů a Big-Omega se používá pouze pro nejlepší případ. Ale při analýze pojmů Big-Theta hovoříme o obou Big-Oh & Big-Omega současně.
tj. Pro Big-Theta je nutné, aby Big-Oh == Big-Omega, jinak nemůžeme mluvit o Big-Theta.
Takže kdekoli (kniha / jakýkoli dokument) vidíte použití Big-Theta, dávají složitost obou Big-Oh & Big-Omega (a oba jsou si také rovni). Ale v mnoha případech nejsou stejné, pak používáme pouze Big- Jen pro nejhorší případ.