Existuje nejaký algoritmus, ktorého veľká O a veľká theta sú odlišné? - algoritmus, časová zložitosť, big-o

Existuje nejaký algoritmus, ktorého veľké O a veľké theta sú odlišné? Zistil som, že sú dosť podobné a mätúce súčasne.

odpovede:

6 pre odpoveď č. 1

Myslím si, že tu časť zmätku pramení zo skutočnosti, že algoritmy nemajú „big-O“ alebo „big-Theta.„O a Θ notácia sa používa na opis dlhodobého tempa rastu funkcií, nie algoritmov. Keď počujete, ako niekto hovorí niečo ako„ binárne vyhľadávanie je O (log n) “,„ čo naozaj “hovoria, je„ runtime “ binárneho vyhľadávania je O (log n) "alebo" najhorší runtime binárneho vyhľadávania na vstupe dĺžky n je O (log n). "

Ďalším dôvodom, prečo to môže byť mätúce, je to, že jedna funkcia môže byť veľkým počtom rôznych funkcií. Napríklad funkcia f (n) = n je O (n), ale je to tiež O (n²), O (n³), O (2ⁿ), atď. Vyplýva to z formálnej definície notácie big-O, ktorá hovorí, že f (n) = O (g (n)), ak (intuitívne) je z dlhodobého hľadiska f (n) ohraničené zhora určitým konštantným násobkom g ( n). To znamená, že môžeme nevyhnutne hovoriť o „veľkom O nejakej funkčnej dobe“, pretože môže existovať nekonečne veľa funkcií, ktoré sa zmestia na účet.

Môžeme povedať nasledujúce: ak je runtime funkcie Θ (f (n)), potom je runtime funkcie tiež O (f (n)). Vyplýva to z definície notácie. Na druhej strane, konverzácia nie je nevyhnutne pravdivá; ak má funkcia runtime O (f (n)), nemusí to byť nevyhnutne prípad, keď je runtime funkcie Θ (f (n)). ako príklad použite binárne vyhľadávanie - binárne vyhľadávanie beží v čase O (log n), ale jeho runtime je tiež O (n) a O (n²), pretože sú to slabšie hranice. Runtime binárneho vyhľadávania však nie je Θ (n), ani nie je Θ (n²) alebo Θ (2ⁿ).

---

2 pre odpoveď č. 2

O (n) predstavuje hornú hranicu algoritmu.

• To znamená, že ako n (vstupná veľkosť), čím väčšia je dĺžka behu algoritmu, alebo O(g(n)), je najviac úmerné g (n).

Θ (n) predstavuje úzku hranicu algoritmu.

• To znamená, že ako n (vstupná veľkosť), čím väčšia je dĺžka behu algoritmu, alebo O(g(n)), je úmerné g (n).

---

Príklad, kde O (n)! = Θ (n)

Rekurzívny prístup k výpočtu n-tej Fibonacciho sekvencie je:

Fib (x) = O (2 ^ n)

Ale tesný viazaný alebo Θ (n), je:

Fib (x) = Θ (Fn)

kde Fn je Fibonacciho sekvencia.

---

Big-O dáva hornú hranicu a nemusí to byť jeden presná odpoveď. Hore hovoríme, že O (Fib (n)) je O(2^n), ale je to tiež O(2^(n^2)) a O(2^(n^n)), ktoré sú hornými hranicami.

Akákoľvek doba behu nad najnižšou dobou behu O (g (n)) je tiež platnou odpoveďou, pretože je stále horná hranica.

Nemôžeme povedať to isté pre Θ(n), pretože je to tesný viazaný.

---

1 pre odpoveď č. 3

O veľkom O môžete uvažovať ako o asymptotickej hornej hranici. A tam je veľká omega pre asymptotickú dolnú hranicu.

Ak je veľká O a veľká Omega identická, je to vo veľkej Thete.

Napríklad môžete uvažovať o algoritmenájsť najväčšie číslo v neusporiadanom poradí dĺžky n. Algoritmus je veľmi jednoduchý, skontroluje číslo pre číslo a uloží aktuálnu maximálnu hodnotu do premennej. V najhoršom prípade musíte skontrolovať každú hodnotu v poradí (je neusporiadaná a najväčšia hodnota je na konci) tak veľká Omega = n. Teraz môžete myslieť na hornú hranicu a mohlo by to byť aj n. Ale napríklad n druhá mocnina je tiež platná horná hranica alebo n! atď.

---