Комплексност у најгорем случају
У рачунарској науци, комплексност у најгорем случају (често се означава у асимптотској нотацији ) мери ресурсе (на пример време извршавања, меморију) који су алгоритму потребни у најгорем случају. Даје горњу границу ресурса потребних алгоритму.
У случају времена за извршавање, комплексност у најгорем случају представља најдуже време извршавања алгоритма за давање било ког уноса н, и тако ово гарантује да ће се алгоритам завршити на време. Штавише, ред раста комплексности у најгорем случају се користи за упоређивање ефикасности два алгоритма.
Комплексност у најгорем случају неког алгоритма треба упоредити са његовиом просечном комплексности, која је количина ресурса које алгоритам користи за насумичан унос.
Дефиниција[уреди | уреди извор]
- За дати модел рачунања и алгоритам A који застаје на сваки унос x, мапирање tA:{0, 1}*→N се зове временска комплексност од A ако, за свако x, A застаје након тачно tA(x) корака.
Док смо често заинтересовани за зависност временске комплексности од различитих дужина уноса, злоупотребљавајућа терминологија, временска комплексност је понекад означена као мапирење TA:N→N, дефинисано са TA(n):= maxx∈{0, 1}n{tA(x)}.
Сличне дефиниције могу да се дају за просторну комплексност, комплексност насумичности и тако даље.
Примери[уреди | уреди извор]
Узмимо у обзир извођење сортирања уметањем на n бројева на насумичној машини. Најбољи случај алгоритма је када су бројеви већ сортирани, што захтева O(n) корака да се изврши задатак. Међутим, улаз за комплексност у најгорем случају је када су бројеви сортирани обрнуто и захтева O(n²) корака да се сортирају; према томе комплексност у најгорем случају insertion sort-а је O(n²).
Види још[уреди | уреди извор]
Референце[уреди | уреди извор]
- 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. стр. 25-27.
- Oded Goldreich. Computational Complexity: A Conceptual Perspective. . Cambridge University Press. 2008. pp. 32. ISBN 978-0-521-88473-0.