Înțeleg matematic $ f (n) \ în O (g (n)) $: $ f (n) $ nu crește mai repede decât $ g (n) $. Mai formal, $ \ există c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
În mod similar, $ f (n) \ in \ Theta (g (n)) $ înseamnă că $ f (n) $ crește aproximativ la fel de repede ca $ g (n) $. adică $ f (n) \ în O (g (n)), \ Omega (g (n)) $.
Ceea ce nu primesc este de ce oamenii folosesc Oh mare pentru timpul de funcționare al un algoritm? Nu ar trebui să folosim Theta mare. Când spunem „Timp de rulare” al unui algoritm, ne referim la cel mai rău timp de rulare, adică $ T (n) = max \ {ALG (x): | x | = n \} $.
Deci, ex: cel mai rău caz de timp de rulare a căutării liniare pe o intrare de dimensiunea $ n $ (elemente $ n $ și o valoare țintă) este $ \ Theta (n) $ și $ O (n) $, dar $ \ Theta (n) $ oferă mai multe informații. Deci, de ce utilizează cărțile de algoritmi $ O (n) $ și nu $ \ Theta (n) $.
Comentarii
- Adesea ‘ s, deoarece pur și simplu nu putem ‘ să obținem o legătură mare-theta strânsă pe timpul de rulare al unui algoritm. Dacă un algoritm este suficient de complicat, s-ar putea întâmpla că cel mai bun lucru pe care îl putem face este să spunem că timpul de rulare este, să spunem $ O (n ^ {n!}) $ Unde în realitate ar putea fi $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Motive istorice.
- ” Ce nu am ‘ nu obține de ce oamenii folosesc Oh mare pentru timpul de funcționare al unui algoritm? ‘ nu ar trebui să folosim Theta mare. ” – Da. Așteptați, nu, ar trebui să facem afirmații și mai precise. Dar dacă trebuie să aleg, da, $ \ Theta $!
Răspuns
Văd două motive pentru care oamenii preferă Big Oh în fața Big Theta:
- Complexitatea runtime a unui algoritm este nu neapărat definită ca fiind cea mai proastă complexitate a runtimei. De asemenea, s-ar putea să-l vedeți doar ca timp de rulare pentru o instanță arbitrară de lungime $ n $. Apoi, dacă scrieți, de exemplu, că timpul de rulare $ t (n) $ al unui algoritm este în $ \ mathcal {O} (n ^ 2) $ aceasta înseamnă că, indiferent de intrarea de lungime $ n $ pe care o alegeți, va crește întotdeauna asimptotic mai lent decât funcția $ c \ cdot n ^ 2 $ pentru o constantă $ c $ – așa că, evident, facem o declarație despre timpul de rulare în cel mai rău caz.
- Uneori, atunci când analizezi timpul de rulare complexitatea unui algoritm pe care nu știți cu siguranță dacă complexitatea cea mai proastă pe care o dați este cu adevărat strânsă. Luați de exemplu complexitatea în timpul rulării multiplicării matricei Acolo nu este încă clar dacă timpul de rulare $ n ^ {2.3728639} $ este într-adevăr cel mai rău caz. Și astfel se știe că timpul de rulare este în $ \ mathcal {O} (n ^ {2.3728639}) $ în timp ce acesta ” nu sunt sigur dacă este în $ \ Theta (n ^ {2.3728639}) $.
Dar, de asemenea, aveți dreptate că, în unele cazuri, ar fi mai bine să furnizați un Big Theta legat decât legat de Big Oh.
Comentarii
- Anunț 1: Cititori, fiți atenți să nu citești prea mult în asta !
Răspunde
O limită superioară (neglijentă) este mai ușor de dovedit decât o limită superioară strânsă, darămite și limitele inferioare.
Unele algoritmi sunt „runtime can” t să fie dat cu aceeași funcție ca limita superioară / inferioară. De exemplu. algoritmii de sortare simpli sunt $ O (n ^ 2) $, dar au limita inferioară $ \ Omega (n) $.
Unii insistă să se străduiască să ofere performanță în termeni asimptotici prin $ \ sim $, unde $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(să spunem ca medie, sau cel mai rău caz, în ceea ce privește numărul unei operații critice, cum ar fi comparații la sortare). Adică, mișcați spațiu, dar nici o constantă (posibil groaznică) nu a măturat sub covor.
Comentarii
- Când ne referim la ” runtime „, ne referim la ceva de genul timpului de rulare cel mai bun caz, al celui mai rău timp de rulare și al timpului mediu de rulare al cazului. De exemplu: Quicksort are $ \ Theta (n ^ 2) $ cel mai rău timp de rulare a cazului și $ \ Theta (n) $ cel mai bun timp de rulare a cazului. Asimptoticele sunt definite în dreapta funcțiilor.
Răspuns
Dacă big-Theta poate fi utilizat în locul big- Oh, ar trebui să fie utilizat dacă nu adaugă dificultăți inutile pentru înțelegere. Există câteva cazuri subtile când big-Theta nu poate fi utilizat în locul big-Oh, de ex .:
Luați în considerare următoarea problemă: sortați matrici de lungime uniformă. Programul pentru rezolvarea acestei probleme ar putea fi: dacă lungimea matricei este ciudată, ieșiți imediat, dacă lungimea matricei este chiar, faceți sortarea cu bule. Care este cel mai rău timp de rulare al acestui algoritm?
Cu siguranță este $ O (n ^ 2) $, dar NU este $ \ Omega (n ^ 2) $ în sensul $ \ Omega $ este de obicei definit. În schimb, cel mai rău timp de rulare este „$ \ Omega (n ^ 2) $ infinit de des” ca să spunem așa (avertisment: terminologie non-standard).
Răspuns
În răspunsul „de ce cărțile de algoritmi folosesc big-Oh și nu Theta”:
Big-Oh este utilizat pentru analiza celui mai rău caz, iar Big-Omega este utilizat numai pentru cel mai bun caz. Dar analizând în termeni de Big-Theta, vorbim atât despre Big-Oh & Big-Omega simultan.
adică. Pentru Big-Theta este necesar ca Big-Oh == Big-Omega, altfel nu putem vorbi despre Big-Theta.
Deci, unde vreodată (carte / orice document) vedeți utilizarea Big-Theta, oferă complexitatea ambelor Big-Oh & Big-Omega (și ambele sunt egale). Dar multe cazuri nu sunt egale atunci folosim doar Big- Oh, doar pentru cel mai rău caz.