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
  1. Aký je najlepší prípad? Ak má pole, ktoré dáme, ako prvú hodnotu 0, bude to trvať konštantný čas: Ω (1)
  2. 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í!

  1. dostať
  2. odstrániť
  3. 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/