Asimptotska složenost (računarstvo)

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

U Teorija složenosti asimptotska složenost u računarstvu je upotreba asimptotske analize za procenu složenosti algoritama i računarskih problema, obično u vezi sa notacijom "Veliko O". U smislu najčešće procenjivanih računarskih resursa, najčešća je vremenska složenost i prostorna složenost.^[1]^[2]

Termin složenost (algoritama) se uglavnom odnosi na asimptotsku složenost.

Dalje, ukoliko nije drugačije naglašeno, termin "računarska složenost" se obično odnosi na gornju granicu asimptotske složenosti algoritma ili problema, koja se obično piše u Veliko-O notaciji; npr. $O(n^{3}).$ Druge vrste procene asimptotske složenosti su notacija donje granice (veliko O | veliko Omega ); npr. Ω(n)) i asimptotski uske procene, kada se gornje i donje granice asimptote poklapaju (koristi se "veliko teta"); npr. Θ(n log n)).

Dalja pretpostavka je da složenost u pitanju je složenost najgoreg slucaja osim ako se drugačije ne naglasi. Alternativni pristup je probabilistička analiza algoritama.

U većni praktičnih slučajeva, radi se o determinističkim algoritama, iako teorijska informatika razmatra nedeterminističke algoritme i druge napredne modele u računarstvu.

Reference

^ Hartmanis, J.; Stearns, R. E. (1965). „On the computational complexity of algorithms”. Transactions of the American Mathematical Society. 117: 285—306. S2CID 40185800. doi:10.1090/S0002-9947-1965-0170805-7.
^ Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.

Vidi još

[1] Hartmanis, J.; Stearns, R. E. (1965). „On the computational complexity of algorithms”. Transactions of the American Mathematical Society. 117: 285—306. S2CID 40185800. doi:10.1090/S0002-9947-1965-0170805-7.

[2] Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.

[1]

[2]