Algoritmiline keerukus

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

Ajalise 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.

Näiteid keerukustest

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(2^n)	Eksponentsiaalne keerukus	Kõigi n-kohaliste kahendsüsteemi arvude tekitamine
O(n!)	Faktoriaalne keerukus	n elemendi kõigi võimalike järjestuste leidmine

Keerukusklassid

• 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.

Välislingid

• Ahto Truu, Programmeerimise alused, Peatükk 5: Algoritmide keerukus