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(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
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

Kategooria:Algoritmid