Asimptotska složenost (računarstvo)

Шаблон:Neprovereni seminarski 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.

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.

Vidi još

• Teorija kompleksnosti
• Master teorema