Azərbaycan  AzərbaycanDeutschland  DeutschlandLietuva  LietuvaMalta  Maltaශ්‍රී ලංකාව  ශ්‍රී ලංකාවTürkmenistan  TürkmenistanTürkiyə  TürkiyəУкраина  Украина
Pagalba
www.datawiki.lt-lt.nina.az
  • Pradžia

Sudėtingumo teorija informatikos šaka nagrinėjanti įvairias algoritmų savybes dažnai jų įvykdymo greitį Teorija atsako į

Algoritmo sudėtingumas

  • Pagrindinis puslapis
  • Algoritmo sudėtingumas
Algoritmo sudėtingumas
www.datawiki.lt-lt.nina.azhttps://www.datawiki.lt-lt.nina.az

Sudėtingumo teorija – informatikos šaka, nagrinėjanti įvairias algoritmų savybes, dažnai jų įvykdymo greitį. Teorija atsako į klausimą kaip palyginti skirtingus algoritmus sprendžiančius tą pačią užduotį (dažniausiai svarbu yra algoritmo veikimo laikas, bet taip pat nagrinėjama kiek algoritmas sunaudoja atminties, ar jis apskritai baigia darbą, ar galima jį vykdyti lygiagrečiai su keliais kompiuteriais), bei kurie algoritmai yra geriausi.

Pagrindiniai algoritmo sudėtingumo kriterijai: trukmė ir sintaksinis algoritmo aprašymas.Algoritmų sudėtingumą galima tirti šiais būdais:

  • Invariantų tyrimas;
  • Asimptotinės išraiškos;

Algoritmų laiko sudėtingumas

Laiko sudėtingumo skaičiavimas vertina, kiek laiko reiktų tam tikrai problemai su tam tikru duomenų dydžiu spręsti efektyviausiu algoritmu. Tarkime, kad turint n bitų duomenų kiekį, problema išsprendžiama per n² žingsnių; tokia problema yra n² sudėtingumo. Iš tiesų, kiekvienas algoritmo įgyvendinimas spręstų problemą skirtingu žingsnių skaičiumi, todėl sąlyginis žingsnių skaičius (eilė) žymima O(n²).

Asimptotinis žymėjimas

O{\displaystyle O} žymėjimas
Asimptotiškai „viršutinė“ riba.
  • Apibrėžtis:f(n)=O(g(n)){\displaystyle f(n)=O(g(n))} jei egzistuoja konstantos c{\displaystyle c} ir n0{\displaystyle n_{0}} tokios, kad cg(n)≥f(n){\displaystyle cg(n)\geq f(n)} visiems n≥n0{\displaystyle n\geq n_{0}}.

O{\displaystyle O} dažniausia naudojamas algoritmo blogiausiam atvejui apibūdinti.

Ω{\displaystyle \Omega } žymėjimas
Asimptotiškai „apatinė“ riba.
  • Apibrėžtis:f(n)=Ω(g(n)){\displaystyle f(n)=\Omega (g(n))} jei egzistuoja konstantos c{\displaystyle c} ir n0{\displaystyle n_{0}} tokios, kad cg(n)≤f(n){\displaystyle cg(n)\leq f(n)} visiems n≥n0{\displaystyle n\geq n_{0}}.

Ω{\displaystyle \Omega } dažniausia apibūdina algoritmo geriausią atvejį arba apatinę ribą.

Θ{\displaystyle \Theta } žymėjimas
Asimptotiškai „ankšta“ riba.
  • Apibrėžtis:f(n)=Θ(g(n)){\displaystyle f(n)=\Theta (g(n))} jei egzistuoja konstantos c1,c2{\displaystyle c_{1},c_{2}} ir n0{\displaystyle n_{0}}, tokios, kad c1g(n)≤f(n)≤c2g(n){\displaystyle c_{1}g(n)\leq f(n)\leq c_{2}g(n)} visiems n≥n0{\displaystyle n\geq n_{0}}.

Asimptotiškai „ankštai“ ribai taip pat galioja savybė, f(n)=Θ(g(n))⟺f(n)=O(g(n))∧f(n)=Ω(g(n)){\displaystyle f(n)=\Theta (g(n))\iff f(n)=O(g(n))\wedge f(n)=\Omega (g(n))}. Asimtotiškai „viršutinė“ riba O(g(n)){\displaystyle O(g(n))} dažnai yra neteisingai naudojama ankštai ribai Θ(g(n)){\displaystyle \Theta (g(n))} apibrėžti, kuri nepadengia Ω(g(n)){\displaystyle \Omega (g(n))} atvejo.

o{\displaystyle o} žymėjimas
Asimptotiškai „negriežta viršutinė“ riba.
  • Apibrėžtis:f(n)=o(g(n)){\displaystyle f(n)=o(g(n))} jei limn→∞(f(n)/g(n))=0{\displaystyle \lim _{n\to \infty }(f(n)/g(n))=0}.
ω{\displaystyle \omega } žymėjimas
Asimptotiškai „negriežta apatinė“ riba.
  • Apibrėžtis:f(n)=ω(g(n)){\displaystyle f(n)=\omega (g(n))} jei limn→∞(f(n)/g(n))=∞{\displaystyle \lim _{n\to \infty }(f(n)/g(n))=\infty }, t. y., g(n)=o(f(n)){\displaystyle g(n)=o(f(n))}.

Žymėjimo ypatumai

Žymėjimas f(n)=O(g(n)){\displaystyle f(n)=O(g(n))}, kai vietoj O{\displaystyle O} gali būti O,o,Θ,Ω,ω{\displaystyle O,o,\Theta ,\Omega ,\omega } yra konceptualiai klaidingas, tačiau yra plačiai naudojamas analizuojant algorithmų sudėtingumą. Korektiškumo dėlei reikėtų vartoti f(n)∈O(g(n)){\displaystyle f(n)\in O(g(n))}

O žymėjimai

Dažniausi algoritmų sudėtingumo žymėjimai ir jų pavadinimai:

Žymėjimas Sudėtingumas Klasė
O(1){\displaystyle O(1)} konstantinis Polinominė (P)
O(log⁡n){\displaystyle O(\log n)} logaritminis
O([log⁡n]c){\displaystyle O([\log n]^{c})} polilogaritminis
O(n){\displaystyle O(n)} tiesinis
O(nlog⁡n){\displaystyle O(n\log n)} supratiesinis
O(n2){\displaystyle O(n^{2})} kvadratinis
O(nc){\displaystyle O(n^{c})} polinominis, kartais geometrinis
O(cn){\displaystyle O(c^{n})} eksponentinis Eksponentinė (NP)
O(n!){\displaystyle O(n!)} faktorialas
O(nn){\displaystyle O(n^{n})} ?

Pavyzdžiai

Paprasčiausių algoritmų sudėtingumo pavyzdžiai:

  • Paieškos algoritmas tiesinėje nesurikiuotų duomenų struktūroje – O(n)
  • Paieškos algoritmas tiesinėje surikiuotų duomenų struktūroje – O(log n)
  • Rikiavimo algoritmas tiesinėje duomenų struktūroje – O(n · log n)

Šaltiniai

  1. algoritmų teorija(parengė Stanislovas Leonas Norgėla). Visuotinė lietuvių enciklopedija (tikrinta 2024-02-03).

Autorius: www.NiNa.Az

Išleidimo data: 25 Lie, 2025 / 18:59

vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Algoritmo sudėtingumas, Kas yra Algoritmo sudėtingumas? Ką reiškia Algoritmo sudėtingumas?

Sudetingumo teorija informatikos saka nagrinejanti įvairias algoritmu savybes daznai ju įvykdymo greitį Teorija atsako į klausima kaip palyginti skirtingus algoritmus sprendziancius ta pacia uzduotį dazniausiai svarbu yra algoritmo veikimo laikas bet taip pat nagrinejama kiek algoritmas sunaudoja atminties ar jis apskritai baigia darba ar galima jį vykdyti lygiagreciai su keliais kompiuteriais bei kurie algoritmai yra geriausi Pagrindiniai algoritmo sudetingumo kriterijai trukme ir sintaksinis algoritmo aprasymas Algoritmu sudetinguma galima tirti siais budais Invariantu tyrimas Asimptotines israiskos Algoritmu laiko sudetingumasLaiko sudetingumo skaiciavimas vertina kiek laiko reiktu tam tikrai problemai su tam tikru duomenu dydziu spresti efektyviausiu algoritmu Tarkime kad turint n bitu duomenu kiekį problema issprendziama per n zingsniu tokia problema yra n sudetingumo Is tiesu kiekvienas algoritmo įgyvendinimas sprestu problema skirtingu zingsniu skaiciumi todel salyginis zingsniu skaicius eile zymima O n Asimptotinis zymejimas O displaystyle O zymejimas Asimptotiskai virsutine riba Apibreztis f n O g n displaystyle f n O g n jei egzistuoja konstantos c displaystyle c ir n0 displaystyle n 0 tokios kad cg n f n displaystyle cg n geq f n visiems n n0 displaystyle n geq n 0 O displaystyle O dazniausia naudojamas algoritmo blogiausiam atvejui apibudinti W displaystyle Omega zymejimas Asimptotiskai apatine riba Apibreztis f n W g n displaystyle f n Omega g n jei egzistuoja konstantos c displaystyle c ir n0 displaystyle n 0 tokios kad cg n f n displaystyle cg n leq f n visiems n n0 displaystyle n geq n 0 W displaystyle Omega dazniausia apibudina algoritmo geriausia atvejį arba apatine riba 8 displaystyle Theta zymejimas Asimptotiskai anksta riba Apibreztis f n 8 g n displaystyle f n Theta g n jei egzistuoja konstantos c1 c2 displaystyle c 1 c 2 ir n0 displaystyle n 0 tokios kad c1g n f n c2g n displaystyle c 1 g n leq f n leq c 2 g n visiems n n0 displaystyle n geq n 0 Asimptotiskai ankstai ribai taip pat galioja savybe f n 8 g n f n O g n f n W g n displaystyle f n Theta g n iff f n O g n wedge f n Omega g n Asimtotiskai virsutine riba O g n displaystyle O g n daznai yra neteisingai naudojama ankstai ribai 8 g n displaystyle Theta g n apibrezti kuri nepadengia W g n displaystyle Omega g n atvejo o displaystyle o zymejimas Asimptotiskai negriezta virsutine riba Apibreztis f n o g n displaystyle f n o g n jei limn f n g n 0 displaystyle lim n to infty f n g n 0 w displaystyle omega zymejimas Asimptotiskai negriezta apatine riba Apibreztis f n w g n displaystyle f n omega g n jei limn f n g n displaystyle lim n to infty f n g n infty t y g n o f n displaystyle g n o f n Zymejimo ypatumai Zymejimas f n O g n displaystyle f n O g n kai vietoj O displaystyle O gali buti O o 8 W w displaystyle O o Theta Omega omega yra konceptualiai klaidingas taciau yra placiai naudojamas analizuojant algorithmu sudetinguma Korektiskumo delei reiketu vartoti f n O g n displaystyle f n in O g n O zymejimai Dazniausi algoritmu sudetingumo zymejimai ir ju pavadinimai Zymejimas Sudetingumas KlaseO 1 displaystyle O 1 konstantinis Polinomine P O log n displaystyle O log n logaritminisO log n c displaystyle O log n c polilogaritminisO n displaystyle O n tiesinisO nlog n displaystyle O n log n supratiesinisO n2 displaystyle O n 2 kvadratinisO nc displaystyle O n c polinominis kartais geometrinisO cn displaystyle O c n eksponentinis Eksponentine NP O n displaystyle O n faktorialasO nn displaystyle O n n Pavyzdziai Paprasciausiu algoritmu sudetingumo pavyzdziai Paieskos algoritmas tiesineje nesurikiuotu duomenu strukturoje O n Paieskos algoritmas tiesineje surikiuotu duomenu strukturoje O logn Rikiavimo algoritmas tiesineje duomenu strukturoje O n log n Saltiniaialgoritmu teorija parenge Stanislovas Leonas Norgela Visuotine lietuviu enciklopedija tikrinta 2024 02 03

Naujausi straipsniai
  • Liepa 26, 2025

    Otto von Mauderodės spaustuvė

  • Liepa 26, 2025

    Ossastorium

  • Liepa 26, 2025

    Osoveco Marijos Dangun Žengimo parapija

  • Liepa 26, 2025

    Osoveco Marijos Dangun Žengimo bažnyčia

  • Liepa 26, 2025

    Osmanli Ankara

www.NiNa.Az - Studija

    Susisiekite
    Kalbos
    Susisiekite su mumis
    DMCA Sitemap
    © 2019 nina.az - Visos teisės saugomos.
    Autorių teisės: Dadash Mammadov
    Nemokama svetainė, kurioje galima dalytis duomenimis ir failais iš viso pasaulio.
    Viršuje