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 predpostavka 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[уреди]

  1. ^ J. Hartmanis, R. Stearns. "On the computational complexity of algorithms," Transactions of the American Mathematical Society, 1965 vol. 117, pp. 285-306
  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.

Vidi još[уреди]