Veliki Omega nam govori donju granicu vremena izvođenja funkcije, a Veliki O nam gornju granicu.
Često su različiti i ne možemo dati jamstvo za vrijeme izvođenja - ono će se razlikovati između dviju granica i ulaza. Ali što se događa kad su isti? Tada možemo dati vezanu theta (Θ) - naša će se funkcija pokretati za to vrijeme, bez obzira na unos koji smo joj dali.
Općenito, uvijek želimo dati theta vezanu ako je moguće jer je to najtočnija i najtješnja veza. Ako ne možemo dati theta vezanu, sljedeća najbolja stvar je najčvršća moguća O veza.
Uzmimo, na primjer, funkciju koja pretražuje niz vrijednosti 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- Koji je najbolji slučaj? Pa, ako niz koji mu dajemo ima kao prvu vrijednost 0, trebat će mu konstantno vrijeme: Ω (1)
- Koji je najgori slučaj? Ako niz ne sadrži 0, ponovit ćemo čitav niz: O (n)
Dali smo mu omegu i O vezu, pa što je s thetaom? Ne možemo mu ga dati! Ovisno o nizu koji mu dajemo, vrijeme izvođenja će biti negdje između konstante i linearnosti.
Promijenimo malo svoj kod.
def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)Možete li se sjetiti najboljeg i najgoreg slučaja ?? Ne mogu! Bez obzira koji mu niz dajemo, moramo prelistati svaku vrijednost u nizu. Dakle, funkcija će trajati BAREM n vremena (Ω (n)), ali isto tako znamo da neće trebati dulje od n vremena (O (n)). Što to znači? Naša funkcija trajat će točno n vremena: Θ (n).
Ako su granice zbunjujuće, razmislite o tome ovako. Imamo 2 broja, x i y. Dobivamo da je x <= y, a da y <= x. Ako je x manje ili jednako y, a y manje ili jednako x, tada x mora biti jednako y!
Ako ste upoznati s povezanim popisima, testirajte se i razmislite o vremenu izvođenja svake od ovih funkcija!
- dobiti
- ukloniti
- dodati
Stvari postaju još zanimljivije kad uzmete u obzir dvostruko povezan popis!
Asimptotska notacija
Kako mjerimo vrijednost izvedbe algoritama?
Razmislite kako nam je vrijeme jedan od najcjenjenijih resursa. U računarstvu možemo mjeriti izvedbu s vremenom potrebno za završetak postupka. Ako su podaci koje obrađuju dva algoritma jednaki, možemo odlučiti o najboljoj implementaciji za rješavanje problema.
To radimo definiranjem matematičkih granica algoritma. To su big-O, big-omega i big-theta, ili asimptotski zapisi algoritma. Na grafikonu bi veliko O bilo najduže što bi algoritam mogao uzeti za bilo koji zadani skup podataka ili "gornju granicu". Big-omega je poput suprotnosti velikom-O, "donjoj granici". Tu algoritam postiže najveću brzinu za bilo koji skup podataka. Velika theta je ili točna vrijednost izvedbe algoritma, ili korisni raspon između uskih gornjih i donjih granica.
Neki primjeri:
- "Dostava će biti tamo tijekom vašeg života." (velika-O, gornja granica)
- "Mogu vam platiti najmanje jedan dolar." (velika omega, donja granica)
- "Najviša temperatura danas će biti 25 ° C, a najniža 19 ° C." (velika-theta, uska)
- "Do plaže je kilometar hoda." (velika-theta, točno)
Više informacija:
//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notacija-predstavlja //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/