| << 1.4 Palju aega algoritmil kulub? | Sisukord | 2 Klassikalised algoritmid >> |
Tunni läbimisel:
- Tean, mis on algoritmi ajaline keerukus
- Oskan leida lihtsamate funktsioonide ajalist keerukust
1.5 Algoritmi keerukus
Kordamine
Eelmises peatükis me koostasime kaks algoritmi Fibonacci arvu leidmiseks. Rekursiivne variant oli küll elegantne, kuid oluliselt aeglasem tsükliga tehtud lahendusest. Kui enamasti me otsime oma probleemi lahendamiseks kiireimat algoritmi, siis milliste teiste omadustega me veel peaksime algoritmi valides arvestama?
- Mälukasutus - mõnikord võib algoritm küll töötada kiiresti, aga kui ta vajab töötamiseks rohkem mälu, kui arvutis vaba ruumi on, siis me ei saa seda kasutada. Näiteks inimese genoomi suurus on 3 miljonit tähemärki ning selle hoidmiseks kulub umbes 700 MB mälu, seega ei saa seda töötlevad algoritmid eriti mälu raisata.
- Õige käitumine ka erandjuhtudel - vahel on tarvis, et algoritm tuleks toime ka negatiivsete arvudega.
- Kõrvalmõjud - mõnikord võivad algoritmidel olla ka kõrvalmõjusid, näiteks järjendil töötav algoritm võib seal olevaid andmeid muuta.
- Lihtsus - kui meie loodud algoritm on väga keeruline, siis on seda ka raske täiendada ja seetõttu peaksime kahe samaväärse algoritmi puhul eelistama loetavamat.
Algoritmide täpse ajakasutuse määramine pole enamasti lihtne ülsanne ning see muutub veelgi keerulisemaks, kui algoritm töötleb palju sisendandmeid. Nimelt, ei pruugi algoritmi kiirus olla alati proportsioonis sisendandmete mahuga. Näiteks algoritm, mis võrdleb kõiki sisendandmeid omavahel, peab andmemahu kahekordsel kasvamisel tegema neli korda rohkem tööd.
Definitsioon: Algoritmi ajaline keerukus näitab, kuidas muutub programmi kiirus programmi sisendandmete kasvades.
Algoritmi ajalist keerukust tähistatakse tähisega {$ O $}, millele järgneb sulgudes keerukusfunktsioon.
Ülesanne 1
Reasta järgmised keerukusfunktsioonid vastavalt sellele, kui kiiresti nad n-i kasvades kasvavad. Järjesta nii, et aeglasemalt kasvavad funktsioonid on enne kiiremini kasvavaid funktsioone. Näiteks {$ O(n) $} kasvab aeglasemalt, kui {$ O(n^2) $}.
- {$ O(n^3) $}
- {$ O(n) $}
- {$ O(2^n) $}
- {$ O(n^2) $}
- {$ O(1) $}
- {$ O(log_2n) $}
- {$ O(n*log_2n) $}
Õige järjestus:
- {$ O(1) $}
- {$ O(log_2n) $}
- {$ O(n) $}
- {$ O(n*log_2n) $}
- {$ O(n^2) $}
- {$ O(n^3) $}
- {$ O(2^n) $}
Algoritmide ajalise keerukuse hindamisel ei huvita meid enamasti, mitu liitmise või korrutamise tehet täpselt tehakse. Meid huvitab ainult see, kui palju aeglasemaks algoritm andmemahu kasvades muutub. Seetõttu hinnatakse ajalist keerukust asümptootiliselt, ehk leitakse selline funktsioon, millest vaadeldava algoritmi töömaht kunagi kiiremini ei kasva. Näiteks kui algoritm võrdleb kõiki sisendandmeid poolte ülejäänud andmetega ja teeb seda 10 korda, siis võime öelda, et selle algoritmi keerukushinnang on {$ O(n^2) $}. Pange tähele, et konstandi 10 võime ära jätta. Täpsema selgituse leiab kursuse algoritmid ja andmestruktuurid õppematerjalidest.
- {$ O(1) $} väljendab näiteks konstantset keerukust, ehk olenemata sellest, kui palju sisendandmeid algoritmile antakse, tehakse alati sama palju operatsioone. Näiteks on konstantse keerukusega funktsiooniks järjendist kõige esimese elemendi leidmine.
- {$ O(n) $} väljendab lineaarset keerukust, mis tähendab, et sisendandmeid läbitakse kindel arv kordi. Näiteks on sellise keerukusega funktsiooniks järjendist minimaalse väärtusega elemendi leidmine.
- {$ O(n^2) $} väljendab ruutkeerukust, mis tähendab, et kõiki elemente võrreldakse ülejäänud elementidega. Näiteks on sellise keerukusega mõned sorteerimismeetodid.
Ülesanne 2
Püüa kirjeldada, mida tähendab keerukus {$ O(n^3) $}. Kui oskad, võid tuua ka näite algoritmist, mis on sellise keerukusega?
{$ O(n^3) $} nimetatakse kuupkeerukuseks, ning selle keerukusega algoritmides võrreldakse kõiki elemente kõigi teiste elementidega ning saadud paare omakorda uuesti kõigi elementidega. Näiteks on sellise keerukusega maatriksite korrutamine.
Ülesanne 3
Leia keerukushinnangud jägmistele funktsioonidele.
- {$ O(1) $}
- {$ O(n) $}
- {$ O(n^2) $}
- {$ O(log_2n) $}
Kui viimane keerukushinnang tuli sulle ootamatuna, siis ilmselt seetõttu, et programm sisaldab ühte tsüklit sarnaselt ülesandele 2. Ometi tasub tähele panna, mida tehakse tsükli sees, sest antud juhul jagatakse iga kord veel teha jäänud sammude arv pooleks. Seega tehakse iga korraga ära justkui pool tööst ning ülesanne saab palju rutemini lahendatud, kui ühekaupa lahendades. Kui algoritm jagab iga korraga allesjäänud töömahu pooleks on tema keerukuseks {$ O(log_2n) $}.
Lisaülesanded
- Koosta algoritm, mis saab ette sõna ja tagastab kõikivõimalikud erinevad tähtede ümberjärjestused. Näiteks sõna "aus" korral tagastatakse: "aus", "asu", "uas", "usa", "sau" ja "sua". Mis on selle funktsiooni ajaline keerukus? (vihje: see on üks konkreetne matemaatiline funktsioon, mida pole sellel lehel mainitud)
- Joonista ülesandes 1 toodud funktsioonide ühele graafikule. Võid kirjutada selle jaoks ka programmi, kasutades näiteks Pythoni teeki matplotlib.
- Koosta algoritm maatriksite korrutamiseks. Leia, mitu tehet tuleb teha kahe 3x3 maatriksi korrutamiseks.
Järgmises Peatükis vaatame klassikaliseid algoritme sagedasti esinevate probleemide lahendamiseks, nagu otsimine ja sorteerimine.
Mõisted:
- keerukus - näitab, kuidas muutub programmi kiirus programmi sisendandmete kasvades.
Viited:
| << 1.4 Kui palju aega algoritmil kulub? | Sisukord | 2 Klassikalised algoritmid >> |