Algoritmiline keerukus
Keerukuse all mõistetakse ajalist või mälumahulist keerukust.
Mälumahuline keerukus näitab, kuidas ülesande lahendamiseks vajalik mälumaht sõltub ülesande mõõdust. Edaspidi vaatleme ainult ajalist keerukust.
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.
Keerukus ei näita seda, kui raske on algoritmi seletada, mõista või programmeerida.
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) | poolitusotsimine | |
| 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) | kõigi n-kohaliste kahendsüsteemi arvude tekitamine |
| O(3n) | kõigi n-kohaliste kolmendsüsteemi arvude tekitamine |
| O(n!) | n elemendi kõigi võimalike järjestuste leidmine |
| O(nn) |
