Skaičiavimo sudėtingumo teorija sutelkia dėmesį į skaičiavimo problemų klasifikavimą pagal jų išteklių naudojimą ir šių klasių susiejimą tarpusavyje. Skaičiavimo problema yra užduotis, kurią išsprendžia kompiuteris. Skaičiavimo problemą galima išspręsti mechaniškai taikant matematinius žingsnius, pvz., algoritmą.
Ką reiškia algoritmo sudėtingumas?
Algoritmo sudėtingumas yra laiko ir (arba) vietos, reikalingo algoritmui tam tikro dydžio (n) įvesties matas,.
Kas yra algoritminis duomenų struktūros sudėtingumas?
Algoritminis sudėtingumas yra matas, nurodantis, kiek laiko užtruks algoritmo užbaigimas, kai įvedamas n dydžio įvestis. Jei algoritmas turi keisti mastelį, jis turėtų apskaičiuoti rezultatą per ribotą ir praktinį laiką, net ir esant didelėms n reikšmėms. Dėl šios priežasties sudėtingumas apskaičiuojamas asimptotiškai, kai n artėja prie begalybės.
Kodėl svarbus algoritminis sudėtingumas?
Kompiuteriai naudoja matematinius sudėtingumo matavimus, kurie leidžia jiems numatyti prieš rašydami kodą, kaip greitai veiks algoritmas ir kiek atminties jam reikės. Tokios prognozės yra svarbūs vadovai programuotojams, įgyvendinantiems ir pasirenkantiems realaus pasaulio taikomųjų programų algoritmus.
Kaip apskaičiuojamas algoritminis sudėtingumas?
Kiekvieno ciklo atveju mes išsiaiškiname juose esančio bloko vykdymo laiką ir padauginame jį iš skaičiaus, kiek kartų programapakartokite kilpą. Visos kilpos, kurios auga proporcingai įvesties dydžiui, turi tiesinį laiko sudėtingumą O(n). Jei pereisite tik per pusę masyvo, tai vis tiek bus O(n).
