Keerukuse hindamise abileht
Kool: Tallinna Tehnikaülikool (TalTech, TTÜ)
Aine: ITI0204 Algoritmid ja andmestruktuurid
Kategooria: Informaatika
Postitatud: 13 jaanuar 2025
Postitaja: TagasihoidlikPart
Kirjeldus
Keerukusklassid Konstante - lahendamise aeg ei sõltu 𝑂(1) sisendi suurusest. Logaritmiline - jagab sisendi igal 𝑂(𝑙𝑜𝑔 𝑛) sammul enam - vähem võrdseteks osadeks Lineaarne - sisend käiakse läbi konstante 𝑂(𝑛) arv kordi. - siia kuuluvad võrdlusi kasutatavad 𝑂(𝑛 𝑙𝑜𝑔 𝑛) sortimisalgoritmid. Ruutkeerukusega - tavaliselt 𝑂(𝑛 2) kahekordse tsükliga algoritmid Kuupkeerukusega - kolmekordse 𝑂(𝑛 3) tsükliga algoritmid Eksponentsiaalne - sisendite 𝑂(2 𝑛) kõikvõimalike alamhulki käiv algoritm Faktoriaalne - sisendi kõikvõimalikud 𝑂(𝑛) permutatsioonide läbi vaatamine. Rusikareegel 1) Konstantse sisuga ühekordne tsükkel on keerukusega 𝑂(𝑛) kahekordne jne ehk kui 𝑂(𝑛 2) kontrollime tsükli muutujat i lineaarset. for (int i 0 i 2 n i) for (int i 100 i n 10 i) for (int i 0 i n i 2) on kõik keerukusega. 𝑂(𝑛) for (int i 0 i (n-2)n i) on ruutkeerukusega . 𝑂(𝑛 2) 2) Kui suurendada/vähendada muutujat i mingi arv korda siis on tegu keerukusega. 𝑂(𝑙𝑜𝑔 𝑛) for (int i 1 i n i2) for (int…