Algoritmo laiko sudėtingumas lemia, kiek laiko algoritmas atlieka vykdymui, priklausomai nuo įvesties užduoties dydžio. Algoritmo laiko sudėtingumas paprastai išreiškiamas naudojant didelį O įrašą, kuris slopina dauginamąsias konstantas ir mažesnius užsakymo terminus.

Kompiuterių moksle algoritmo laiko sudėtingumas apskaičiuoja laiką, praleistą algoritme vykdant, priklausomai nuo įvesties problemos dydžio. Algoritmo laiko sudėtingumas paprastai išreiškiamas naudojant didelę reikšmę „ O“ , kuri slopina dauginamąsias konstantas ir mažesnes eilės sąlygas.

Tokiu būdu išreiškiama, kad laiko sudėtingumas apibūdinamas asimptotiškai, t.y. kai įvesties signalo dydis pereina į begalybę. Pvz., Jei laikas, kurio reikalaujama algoritmuose visuose įėjimuose, kurių dydis yra n, neviršija 5n^3 + 3n , asimptotinio laiko sudėtingumas yra O(n^3) .

Laiko sudėtingumas paprastai apskaičiuojamas skaičiuojant algoritmo atliekamų elementarių operacijų skaičių, kai pradinė operacija užima tam tikrą laiką. Taigi laiko ir pradinių operacijų, kurias atlieka algoritmas, skaičius skiriasi ne daugiau kaip pastoviu veiksniu.

Kadangi algoritmas gali užtrukti skirtingus laiko momentus net to paties dydžio įvestyse, dažniausiai naudojamas laiko komplekso matas, blogiausias laiko algoritmo sudėtingumas, žymimas kaip T(n) , tai yra didžiausias laikas, praleistas bet kuriam įvesties dydžiui n . Laiko sudėtingumas klasifikuojamas pagal T(n) funkcijos pobūdį.

Pavyzdžiui, algoritmas su T(n) = O(n) yra vadinamas tiesiniu laiko algoritmu, o algoritmas su T(n) = O(2^n) vadinamas eksponentiniu laiko algoritmu.

Naudingos nuorodos:

Susijusios žymės: