Algoritmiline keerukus
Artiklis ei ole piisavalt viiteid. |
Algoritmiline keerukus näitab, kuidas muutub programmi kiirus ja kasutatav mälumaht programmi sisendandmete kasvades. Algoritmiline keerukus pole seotud sellega, kui raske on algoritmi seletada, mõista või programmeerida. Mälumahuline keerukus näitab, kuidas ülesande lahendamiseks vajalik mälumaht sõltub ülesande mõõdust. Ajaline keerukus näitab, kuidas ülesande (algoritmi) tööaeg sõltub ülesande mõõdust (s.t. lähteandmete hulgast). Analoogiliselt räägitakse programmeerimises programmi, alamprogrammi või programmilõigu keerukusest.
Ajaline keerukus
muudaAjalise keerukuse tähis on O, millele järgneb sulgudes keerukusfunktsioon.
Eristatakse head ehk polünomiaalset keerukust, mida väljendab polünoom, ja halba ehk mittepolünomiaalset keerukust, mida polünoomiga ei saa väljendada. Piltlikult öeldes on headel keerukustel astendaja konstantne, aga halbadel keerukustel läheb n astendajasse. Heade keerukuste kohta võib öelda, et kui algoritmi keerukus on O(f(n)), siis ülesande mõõdu suurenemisel n korda ei suurene tööaeg rohkem kui f(n) korda.
Polünomiaalseid keerukusi nimetatakse sellepärast headeks, et kui ülesande maht on liiga suur, siis on kasu kiiremast raalist. Mittepolünomiaalseid keerukusi nimetatakse halbadeks, sest siis kiirem raal praktiliselt ei suurenda tööjõudlust. Ainus, mis aitab, on algoritmi asendamine kiiremaga, kuid see ei ole alati võimalik.
| O(1) | Triviaalne keerukus | Paisksalvestus |
| O(log2n) | Logaritmiline keerukus | Kahendotsing |
| O(n) | lineaarne keerukus | Vektorite sisestamine, väljastamine, liitmine, lahutamine ja skalaarkorrutamine |
| O(n*log2n) | Poolitussortimine, kiirsortimine | |
| O(n*√n) | Shelli sortimine | |
| O(n²) | Ruutkeerukus | Maatriksite sisestamine, väljastamine, liitmine ja lahutamine, mullsortimine, valiksortimine |
| O(n³) | Kuupkeerukus | Maatriksite korrutamine |
| O(2n) | Eksponentsiaalne keerukus | Kõigi n-kohaliste kahendsüsteemi arvude tekitamine |
| O(n!) | Faktoriaalne keerukus | n elemendi kõigi võimalike järjestuste leidmine |
Keerukusklassid
muuda- Keerukusklass P. Keel A kuulub keerukusklassi P, kui leidub polünoom p(x) ja deterministlik Turingi masin M ajakeerukusega p(x), mis tuvastab keele A.
- Keerukusklass NP. Keel A kuulub keerukusklassi NP kui leidub polünoom p(x) ja mittedeterministlik Turingi masin M ajakeerukusega p(x), mis tuvastab keele A.
- Keerukusklass PSPACE. Keel A kuulub keerukusklassi PSPACE, kui leidub polünoom p(x) ja deterministlik Turingi masin M mälukeerukusega p(x), mis tuvastab keele A.