Šioje pamokoje sužinosite, kas yra asimptotiniai žymėjimai. Taip pat sužinosite apie „Big-O“, „Theta“ ir „Omega“ žymėjimą.
Algoritmo efektyvumas priklauso nuo laiko, saugyklos ir kitų išteklių, reikalingų algoritmui vykdyti, kiekio. Efektyvumas matuojamas asimptotinių užrašų pagalba.
Algoritmas gali nevienodai atlikti skirtingų tipų įvestis. Padidėjus įvesties dydžiui, našumas pasikeis.
Algoritmo našumo pokyčio tyrimas su įvesties dydžio pasikeitimu apibrėžiamas kaip asimptotinė analizė.
Asimptotiniai užrašai
Asimptotiniai žymėjimai yra matematiniai žymėjimai, naudojami algoritmo veikimo laikui apibūdinti, kai įvestis linksta prie tam tikros vertės arba ribinės vertės.
Pvz., Kai burbulų rūšiavimas, kai įvesties masyvas jau yra rūšiuojamas, algoritmo laikas yra tiesinis, ty geriausiu atveju.
Tačiau, kai įvesties masyvas yra atvirkštinės būklės, algoritmas surenka maksimalų laiką (kvadratinį) elementų rūšiavimui, ty blogiausiu atveju.
Kai įvesties masyvas nėra nei rūšiuojamas, nei atvirkštine tvarka, tai užtrunka vidutiniškai. Šios trukmės žymimos naudojant asimptotinius žymėjimus.
Iš esmės yra trys asimptotiniai žymėjimai:
- Big-O žymėjimas
- Omega žymėjimas
- Teta žymėjimas
„Big-O“ žymėjimas („O-notation“)
„Big-O“ žymėjimas rodo viršutinę algoritmo veikimo laiko ribą. Taigi tai suteikia blogiausiu atveju algoritmo sudėtingumą.
„Big-O“ suteikia viršutinę funkcijos ribą
O (g (n)) = (f (n): egzistuoja teigiamos konstantos c ir n 0 , kad 0 ≦ f (n) ≦ cg (n) visiems n ≧ n 0 )
Aukščiau išraiška gali būti apibūdinta kaip funkcija f(n)priklauso rinkinio O(g(n))jei egzistuoja teigiamas konstanta ctokia, kad ji yra tarp 0ir cg(n)už pakankamai didelė n.
Bet kuriai reikšmei nalgoritmo veikimo laikas neperžengia nurodyto laiko O(g(n)).
Kadangi tai suteikia blogiausią algoritmo veikimo laiką, jis plačiai naudojamas algoritmui analizuoti, nes mus visada domina blogiausias scenarijus.
„Omega“ žymėjimas (Ω žymėjimas)
„Omega“ žymėjimas reiškia apatinę algoritmo veikimo laiko ribą. Taigi tai užtikrina geriausią algoritmo sudėtingumą.
„Omega“ suteikia apatinę funkcijos ribą
Ω (g (n)) = (f (n): egzistuoja teigiamos konstantos c ir n 0 , kad 0 ≦ cg (n) ≦ f (n) visiems n ≧ n 0 )
Pirmiau pateiktą išraišką galima apibūdinti kaip funkciją, f(n)priklausančią rinkiniui, Ω(g(n))jei egzistuoja teigiama konstanta c, kuri yra cg(n)pakankamai didelė n.
Bet kuriai reikšmei nminimalų algoritmui reikalingą laiką nurodo „Omega“ Ω(g(n)).
Theta žymėjimas ((-notacija)
Teta žymėjimas apima funkciją iš viršaus ir iš apačios. Kadangi tai reiškia viršutinę ir apatinę algoritmo veikimo laiko ribas, ji naudojama analizuojant algoritmo vidutinį sudėtingumą.
Teta riboja funkciją konstantų veiksnių ribose
Dėl funkcija g(n), Θ(g(n))yra apskaičiuojamas pagal atžvilgiu:
Θ (g (n)) = (f (n): egzistuoja teigiamos konstantos c 1 , c 2 ir n 0 , kad 0 0 c 1 g (n) ≦ f (n) ≦ c 2 g (n) visiems n ≧ n 0 )
Aukščiau išraiška gali būti apibūdinta kaip funkcija f(n)priklauso rinkinio Θ(g(n)), jei egzistuoja teigiami konstantas ir taip, kad ji gali būti įtvirtinta tarp ir už pakankamai didelis n.c1c2c1g(n)c2g(n)
Jei funkcija f(n)slypi bet kur tarp jų ir visiems , tada sakoma, kad ji yra asimptotiškai griežta.c1g(n)c2g(n)n ≧ n0f(n)
