Kompleksnost u najgorem slučaju

U računarskoj nauci, kompleksnost u najgorem slučaju (često se označava u asimptotskoj notaciji ) meri resurse (na primer vreme izvršavanja, memoriju) koji su algoritmu potrebni u najgorem slučaju. Daje gornju granicu resursa potrebnih algoritmu.

U slučaju vremena za izvršavanje, kompleksnost u najgorem slučaju predstavlja najduže vreme izvršavanja algoritma za davanje bilo kog unosa n, i tako ovo garantuje da će se algoritam završiti na vreme. Štaviše, red rasta kompleksnosti u najgorem slučaju se koristi za upoređivanje efikasnosti dva algoritma.

Kompleksnost u najgorem slučaju nekog algoritma treba uporediti sa njegoviom prosečnom kompleksnosti, koja je količina resursa koje algoritam koristi za nasumičan unos.

Definicija

Za dati model računanja i algoritam A koji zastaje na svaki unos x, mapiranje t_A:{0, 1}*→N se zove vremenska kompleksnost od A ako, za svako x, A zastaje nakon tačno t_A(x) koraka.

Dok smo često zainteresovani za zavisnost vremenske kompleksnosti od različitih dužina unosa, zloupotrebljavajuća terminologija, vremenska kompleksnost je ponekad označena kao mapirenje T_A:N→N, definisano sa T_A(n):= max_{x∈{0, 1}ⁿ}{t_A(x)}.

Slične definicije mogu da se daju za prostornu kompleksnost, kompleksnost nasumičnosti i tako dalje.

Primeri

Uzmimo u obzir izvođenje sortiranja umetanjem na n brojeva na nasumičnoj mašini. Najbolji slučaj algoritma je kada su brojevi već sortirani, što zahteva O(n) koraka da se izvrši zadatak. Međutim, ulaz za kompleksnost u najgorem slučaju je kada su brojevi sortirani obrnuto i zahteva O(n²) koraka da se sortiraju; prema tome kompleksnost u najgorem slučaju insertion sort-a je O(n²).

Vidi još

• Analiza algoritama

Reference

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. 2001. ISBN 978-0-262-03293-3. Chapter 2.2: Analyzing algorithms. str. 25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. . Cambridge University Press. 2008. pp. 32. ISBN 978-0-521-88473-0.