Šajā apmācībā jūs uzzināsiet, kas ir asimptotiskie apzīmējumi. Jūs arī uzzināsiet par Big-O notāciju, Theta notāciju un Omega notāciju.
Algoritma efektivitāte ir atkarīga no laika, krātuves un citu resursu apjoma, kas nepieciešams algoritma izpildei. Efektivitāti mēra ar asimptotisku apzīmējumu palīdzību.
Algoritmam var nebūt vienāda veiktspēja dažādiem ievades veidiem. Palielinoties ievades lielumam, veiktspēja mainīsies.
Pētījums par izmaiņām algoritma veiktspējā ar izmaiņām ievades lieluma secībā ir definēts kā asimptotiska analīze.
Asimptotiski apzīmējumi
Asimptotiskie apzīmējumi ir matemātiskie apzīmējumi, ko izmanto, lai aprakstītu algoritma darbības laiku, kad ievade virzās uz noteiktu vērtību vai ierobežojošu vērtību.
Piemēram: burbuļu kārtošanā, kad ievades masīvs jau ir sakārtots, algoritma patērētais laiks ir lineārs, ti, labākais gadījums.
Bet, ja ievades masīvs ir apgrieztā stāvoklī, algoritmam elementu kārtošanai, ti, sliktākajā gadījumā, ir vajadzīgs maksimālais laiks (kvadrātiskais).
Ja ievades masīvs nav ne kārtots, ne apgrieztā secībā, tam nepieciešams vidējais laiks. Šie ilgumi tiek apzīmēti, izmantojot asimptotiskus apzīmējumus.
Galvenokārt ir trīs asimptotiski apzīmējumi:
- Big-O apzīmējums
- Omega apzīmējums
- Teta apzīmējums
Big-O apzīmējums (O-notation)
Big-O apzīmējums apzīmē algoritma darbības laika augšējo robežu. Tādējādi tas nodrošina vissliktāko algoritma sarežģītību.
Big-O dod funkcijas augšējo robežu
O (g (n)) = (f (n): pastāv pozitīvas konstantes c un n 0, piemēram, ka 0 ≦ f (n) ≦ cg (n) visiem n ≧ n 0 )
Iepriekš minēto izteicienu var raksturot kā funkciju, kas f(n)pieder kopai, O(g(n))ja pastāv pozitīva konstante, ckas atrodas starp 0un cg(n)pietiekami lielai n.
nAlgoritma darbības laiks nevienai vērtībai nepārsniedz norādīto laiku O(g(n)).
Tā kā tas dod algoritma sliktāko darbības laiku, to plaši izmanto algoritma analīzei, jo mūs vienmēr interesē vissliktākais scenārijs.
Omega apzīmējums (Ω-apzīmējums)
Omega apzīmējums apzīmē algoritma darbības laika apakšējo robežu. Tādējādi tas nodrošina vislabāko algoritma sarežģītību.
Omega dod funkcijas apakšējo robežu
Ω (g (n)) = (f (n): pastāv tādas pozitīvas konstantes c un n 0, ka visiem n ≧ n 0 ir 0 ≦ cg (n) ≦ f (n )
Iepriekš minēto izteiksmi var raksturot kā funkciju, kas f(n)pieder kopai, Ω(g(n))ja pastāv pozitīva konstante, clai tā cg(n)būtu pietiekami liela n.
Jebkurai vērtībai nminimālo algoritmā nepieciešamo laiku norāda Omega Ω(g(n)).
Teta apzīmējums (Θ-apzīmējums)
Teta apzīmējums ietver funkciju no augšas un apakšas. Tā kā tā apzīmē algoritma darbības laika augšējo un apakšējo robežu, to izmanto algoritma vidējās sarežģītības analīzei.
Teta ierobežo funkciju konstantu faktoros
Par funkciju g(n), Θ(g(n))tiek dots ar sakarību:
Θ (g (n)) = (f (n): pastāv pozitīvas konstantes c 1 , c 2 un n 0, piemēram, ka 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) visiem n ≧ n 0 )
Iepriekš minēto izteiksmi var raksturot kā funkciju, kas f(n)pieder kopai, Θ(g(n))ja pastāv pozitīvas konstantes, un tā, ka to var ievietot starp un , pietiekami lielam n.c1c2c1g(n)c2g(n)
Ja funkcija f(n)atrodas kaut kur pa vidu un visiem , tad tiek teikts, ka tā ir asimptotiski cieši saistīta.c1g(n)c2g(n)n ≧ n0f(n)
