Vysvetlená veľká theta a asymptotická notácia
Big Omega nám hovorí dolnú hranicu behu funkcie a Big O nám hornú hranicu.
Často sú odlišné a nemôžeme poskytnúť záruku na dobu behu - bude sa líšiť medzi dvoma hranicami a vstupmi. Čo sa však stane, keď sú rovnaké? Potom môžeme dať viazanú theta (Θ) - naša funkcia bude v tom čase bežať bez ohľadu na to, aký vstup jej dáme.
Všeobecne vždy chceme dať thétu, ak je to možné, pretože je to najpresnejšia a najtesnejšia väzba. Ak nemôžeme dať viazanú thétu, ďalšou najlepšou vecou je najtesnejšia možná väzba.
Vezmime si napríklad funkciu, ktorá v poli vyhľadá hodnotu 0:
def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false- Aký je najlepší prípad? Ak má pole, ktoré dáme, ako prvú hodnotu 0, bude to trvať konštantný čas: Ω (1)
- Aký je najhorší prípad? Ak pole neobsahuje 0, budeme iterovať cez celé pole: O (n)
Dali sme tomu omegu a O viazané, tak čo theta? Nemôžeme mu dať ani jeden! V závislosti od poľa, ktoré mu dáme, bude runtime niekde medzi konštantnou a lineárnou.
Poďme trochu zmeniť náš kód.
def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)Napadá vás najlepší a najhorší prípad ?? Nemôžem! Bez ohľadu na to, aké pole mu dáme, musíme iterovať cez každú hodnotu v poli. Funkcia teda bude NÍMTO trvať n (Ω (n)), ale tiež vieme, že to nebude trvať dlhšie ako n času (O (n)). Čo to znamená? Naša funkcia bude trvať presne n času: Θ (n).
Ak sú hranice mätúce, premýšľajte o tom takto. Máme 2 čísla, xay. Udáva sa, že x <= y a že y <= x. Ak je x menšie alebo rovné y a y menšie alebo rovné x, potom x sa musí rovnať y!
Ak sú vám prepojené zoznamy známe, otestujte sa a porozmýšľajte o časových obdobiach každej z týchto funkcií!
- dostať
- odstrániť
- pridať
Veci budú ešte zaujímavejšie, keď vezmete do úvahy dvojnásobne prepojený zoznam!
Asymptotická notácia
Ako meriame výkonovú hodnotu algoritmov?
Zvážte, ako je čas jedným z našich najcennejších zdrojov. Vo výpočtovej technike môžeme merať výkon s dĺžkou času potrebného na dokončenie procesu. Ak sú údaje spracované dvoma algoritmami rovnaké, môžeme rozhodnúť o najlepšej implementácii riešenia problému.
Robíme to definovaním matematických limitov algoritmu. Toto sú big-O, big-omega a big-theta alebo asymptotické zápisy algoritmu. V grafe by big-O bol najdlhší, aký by algoritmus mohol trvať pre akýkoľvek daný súbor údajov, alebo „hornú hranicu“. Big-omega je ako opak veľkého-O, „dolnej hranice“. To je miesto, kde algoritmus dosahuje najvyššiu rýchlosť pre ľubovoľnú množinu údajov. Veľká theta je buď presná hodnota výkonu algoritmu, alebo užitočný rozsah medzi úzkou hornou a dolnou hranicou.
Niekoľko príkladov:
- "Dodávka bude tam počas vášho života." (veľká-O, horná hranica)
- "Môžem ti zaplatiť aspoň jeden dolár." (veľká-omega, dolná hranica)
- „Dnes bude najvyššia teplota 25 ° C a najnižšia teplota 19 ° C.“ (veľká-theta, úzka)
- "Je to kilometer chôdze od pláže." (veľká-théta, presná)
Viac informácií:
//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% Notácia A8 predstavuje //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/
