Najbolji, najgori i prosečan slučaj
U informatici najbolji, najgori i prosečan slučaj datog algoritma izražavaju redom najbolju, najgoru i prosečnu iskorišćenost resursa. Pod resursom se obično podrazumeva vreme izvršavanja programa, ali resurs može biti i količina zauzete memorije prilikom izvršavanja programa.
Što se tiče izvršavanja programa u realnom vremenu (engl. real-time computing), složenost najgoreg slučaja je često od presudne važnosti pri konstrukciji algoritma, jer je veoma važno znati za koje vreme će program završiti svoj rad.
U analizi algoritama najčešće se ispitiju performanse prosečnog i najgoreg slučaja. Performanse najboljeg slučaja se ređe ispituju.
Ovi pojmovi se koriste i u drugačijim kontekstima, na primer: najbolji i najgori slučaj širenja epidemije, požara itd.
Performanse najboljeg slučaja nekog algoritma uredi
U informatici ovaj termin se koristi za opis ponašanja algoritma u optimalnim uslovima. Na primer, najbolji slučaj za linearnu pretragu niza je kada se traženi element nalazi na prvoj poziciji niza.
Konstrukcija i izbor algoritma se retko zasniva na performansi u najboljem slučaju, već se programeri najčešće trude da poboljšaju performanse algoritma u prosečnom i najgorem slučaju.
Poređenje performansi najgoreg i prosečnog slučaja uredi
Analiza najgoreg i prosečnog slučaja imaju određene sličnosti, ali u praksi obično zahtevaju drugačije alate i pristupe.
Teško je odrediti prosečni ulaz za neki algoritam, jer taj prosečni ulaz često ima određene osobine koje se teško matematički opisuju (primer: algoritmi koji kao ulaznu vrednost primaju tekstualni sadržaj (engl. string) ). Čak i kada je moguće opisati određeni prosečni slučaj, često se dešava da se kao rezultat dobiju komplikovane jednačine.
Slični problemi se javljaju i kod analize najgoreg slučaja. Često je nemoguće odrediti tačne uslove najgoreg slučaja, pa se kao takvi uzimaju uslovi koji su „dovoljno loši“ da predstavljaju najgori slučaj. Na primer, pri analizi određenog algoritma moguće je odrediti najduži mogući put kroz taj algoritam (posmatrajući maksimalni broj petlji u koje se ulazi) čak i ako nije moguće odrediti tačnu vrednost ulaza koji bi proizveo takav put kroz algoritam. Ovakav pristup daje sigurnu analizu algoritma, jer se provereno neće pojaviti vrednost ulaza koja bi zahtevala više resursa od najgoreg slučaja.
U nekim situacijama je neophodno primeniti ovakav pristup analizi algoritma da bi sigurnost algoritma bila garantovana, međutim u slučajevima kada se zna da je mala verovatnoća da će doći do greške pri nekim uslovima, moguće zanemariti takve uslove. Ovaj pristup se smatra optimističnim jer zanemaruje pravi najgori slučaj, već za najgori slučaj uzima slučaj koji je „dovoljno loš“ i može biti dosta praktičniji.
Analiza najgoreg slučaja je usko povezana sa složenošću najgoreg slučaja.
Primeri uredi
- Algoritmi sortiranja[1]:
| Algoritam | Struktura podataka | Vremenska složenost:najbolja | Vremenska složenost:prosečna | Vremenska složenost:najgora | Prostorna složenost:najgora |
|---|---|---|---|---|---|
| Kviksort | Niz | O(n log(n)) | O(n log(n)) | O(n2) | O(n log(n)) |
| Sortiranje sa spajanjem | Niz | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Metod mehura | Niz | O(n) | O(n2) | O(n2) | O(1) |
| Sortiranje ubacivanjem | Niz | O(n) | O(n2) | O(n2) | O(1) |
- Linearna pretraga liste od n elemenata. U najgorem slučaju svaki element liste će biti posećen jednom. U tom slučaju traženi elemen se nalazi na kraju liste ili se ne nalazi u listi. U prosečnom slučaju, pod pretpostavkom da se traženi element nalazi u listi, svaki od elemenata ima jednaku šansu da je upravo on tražen, program vrši proveru za n/2 elemenata.
- Kviksort primenjen na listi od n elemenata, pod pretpostavkom da su svi elementi različiti i raspoređeni u slučajnom redosledu, u prosečnom slučaju daje složenost O(n log(n)). Međutim u najgorem slučaju kada su elementi u listi sortirani u obrnutom redosledu, složenost opada na O(n2).