Најбољи, најгори и просечан случај
У информатици најбољи, најгори и просечан случај датог алгоритма изражавају редом најбољу, најгору и просечну искоришћеност ресурса. Под ресурсом се обично подразумева време извршавања програма, али ресурс може бити и количина заузете меморије приликом извршавања програма.
Што се тиче извршавања програма у реалном времену (енгл. real-time computing), сложеност најгорег случаја је често од пресудне важности при конструкцији алгоритма, јер је веома важно знати за које време ће програм завршити свој рад.
У анализи алгоритама најчешће се испитију перформансе просечног и најгорег случаја. Перформансе најбољег случаја се ређе испитују.
Ови појмови се користе и у другачијим контекстима, на пример: најбољи и најгори случај ширења епидемије, пожара итд.
Перформансе најбољег случаја неког алгоритма
[уреди | уреди извор]У информатици овај термин се користи за опис понашања алгоритма у оптималним условима. На пример, најбољи случај за линеарну претрагу низа је када се тражени елемент налази на првој позицији низа.
Конструкција и избор алгоритма се ретко заснива на перформанси у најбољем случају, већ се програмери најчешће труде да побољшају перформансе алгоритма у просечном и најгорем случају.
Поређење перформанси најгорег и просечног случаја
[уреди | уреди извор]Анализа најгорег и просечног случаја имају одређене сличности, али у пракси обично захтевају другачије алате и приступе.
Тешко је одредити просечни улаз за неки алгоритам, јер тај просечни улаз често има одређене особине које се тешко математички описују (пример: алгоритми који као улазну вредност примају текстуални садржај (енгл. string) ). Чак и када је могуће описати одређени просечни случај, често се дешава да се као резултат добију компликоване једначине.
Слични проблеми се јављају и код анализе најгорег случаја. Често је немогуће одредити тачне услове најгорег случаја, па се као такви узимају услови који су „довољно лоши“ да представљају најгори случај. На пример, при анализи одређеног алгоритма могуће је одредити најдужи могући пут кроз тај алгоритам (посматрајући максимални број петљи у које се улази) чак и ако није могуће одредити тачну вредност улаза који би произвео такав пут кроз алгоритам. Овакав приступ даје сигурну анализу алгоритма, јер се проверено неће појавити вредност улаза која би захтевала више ресурса од најгорег случаја.
У неким ситуацијама је неопходно применити овакав приступ анализи алгоритма да би сигурност алгоритма била гарантована, међутим у случајевима када се зна да је мала вероватноћа да ће доћи до грешке при неким условима, могуће занемарити такве услове. Овај приступ се сматра оптимистичним јер занемарује прави најгори случај, већ за најгори случај узима случај који је „довољно лош“ и може бити доста практичнији.
Анализа најгорег случаја је уско повезана са сложеношћу најгорег случаја.
Primeri
[уреди | уреди извор]- Алгоритми сортирања[1]:
| Алгоритам | Структура података | Временска сложеност:најбоља | Временска сложеност:просечна | Временска сложеност:најгора | Просторна сложеност:најгора |
|---|---|---|---|---|---|
| Квиксорт | Низ | O(n log(n)) | O(n log(n)) | O(n2) | O(n log(n)) |
| Сортирање са спајањем | Низ | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Метод мехура | Низ | O(n) | O(n2) | O(n2) | O(1) |
| Сортирање убацивањем | Низ | O(n) | O(n2) | O(n2) | O(1) |
- Линеарна претрага листе од n елемената. У најгорем случају сваки елемент листе ће бити посећен једном. У том случају тражени елемен се налази на крају листе или се не налази у листи. У просечном случају, под претпоставком да се тражени елемент налази у листи, сваки од елемената има једнаку шансу да је управо он тражен, програм врши проверу за n/2 елемената.
- Квиксорт примењен на листи од n елемената, под претпоставком да су сви елементи различити и распоређени у случајном редоследу, у просечном случају даје сложеност O(n log(n)). Међутим у најгорем случају када су елементи у листи сортирани у обрнутом редоследу, сложеност опада на O(n2).