Algoritmi ajaline keerukus
2. Algoritmi ajaline keerukus (jätk)
2.1. Olulisemad mõisted ([J.Kiho] põhjal )
Def: Algoritmi ajalist keerukust väljendab funktsioon f, mis igale antud algoritmi järgi
lahendatavale konkreetsele ülesandele andmemahuga n seab vastavusse ülesande
lahendamisel sooritatavate algoritmi sammude arvu f(n).
Üldiselt eeldatakse,et antud algoritmi alusel koostatud programmide töö aeg on ajalise
keerukuse funktsiooni kordne c*f(n), kus c on konstant.
Eriti oluline on algoritmi ajalist keerukust väljendava funktsiooni käitumine alg-
andmete mahu piiramatul kasvamisel. Vastavat hinnangut nimetatakse
asümptootiliseks hinnanguks.
Lahendusaja suhtelist kasvu kirjeldab järgmine tabel:
Programmi töö aeg kujul c*f(n) Lahendamise aja suhteline kasv f(25)/f(5)
c1*log(n) 2
c2*n2 25
c3*n3 125
c4*2n ...
annaabi.ee 
