| << 1.2 Rekursiivsed algoritmid | Sisukord | 1.4 Algoritmi keerukus >> |
Tunni läbimisel:
- Tean kuidas hinnata algoritmi kiirust
1.4 Kui palju aega algoritmil kulub?
Peamine küsimus, mis meil algoritmide koostamisel tekib, on see, kui kaua nad aega võtavad. Siis me teame, kas jõuame vahepeal endale kohvi keeta, või võtab meie koostatud algoritm nii palju aega, et suuremate ülesannete puhul ei lõpeta see kunagi oma tööd. Näiteks kohe kindlasti me ei taha, et meie e-poodi sisse logimine võtaks üle minuti aega, sest siis lähevad meie kliendid lihtsalt konkurendi juurde.
Ülesanne 1
Fibonacci arvuks {$ F_n $} nimetatakse rekursiivselt tuletatud arvu: {$ F_n = F_{n-1} + F_{n-2} $}, mille algväärtused on {$ F_1 = 1 $} ja {$ F_2 = 1 $}. Analoogselt eelmises tunnis koostatud faktoriaali leidmise algoritmile, koosta funktsioon Fibonacci arvu leidmiseks. Kasuta seda funktsiooni, et arvutada Fibonacci arv {$ F_{14} $}.
- Siin on toodud Fibonacci arvu leidmise funktsioon, milles on puudu rekursiooni samm:
- Kontrollimiseks võid proovida {$ F_{10} = 55 $}
Igapäevaülesannete puhul saame me üsna lihtsasti leida, kui palju nad aega võtavad. Näiteks kui me teame, et meil kulub ühe taldriku pesemiseks 30 sekundit, saame kergesti välja arvutada, palju kulub aega terve virna pesemiseks. Digitaalsete ülesannete puhul on olukord tegelikult sarnane. Arvuti protsessori taktsagedus, mis on antud gigahertsides (GHz) näitab umbes, kui palju tehteid arvuti ühe sekundi jooksul teha suudab, näiteks 1GHz ühetuumaline protsessor teeb sekundis umbes {$ 10^{9} $} elementaartehet. Paraku ei saa niimoodi kuluvat aega täpselt arvutada, sest see sõltub veel paljudest muudest asjaoludest. Näiteks oskavad arvutid vahel teha mitu operatsiooni korraga, või peavad hoopiski ootama, kuni andmeid mälust loetakse. Siiski saab andmemahtu teades anda hinnangu, kui palju võiks algoritmil ülesande lahendamiseks aega kuluda.
Ülesanne 2
Eelmises ülesandes koostatud Fibonacci arvu leidmise algoritm leiab {$ F_{10} $} ülikiiresti, kahjuks on see suuremate sisendite korral väga aeglane, miks?
Ligikaudse liitmistehete arvu, mida {$ F_n $} arvutamiseks tuleb teha saab leida valemiga:
Selle valemi kohaselt on vaja 1000-nda Fibonacci arvu leidmiseks teha {$ 4.8 \times 10^{208} $} liitmistehet.
Oletame, et sul on kasutada superarvuti, mis suudab teha {$ 10^{15} $} liitmistehet sekundis (see on umbes tänapäevase superarvuti võimsus). Kui palju aega kulub, et arvutada {$ F_{1000} $}? Kas see võtab aega:
- alla sekundi;
- mõned minutid;
- mõni päev;
- mõni aasta või
- kauem kui universumi vanus
- Matemaatika tunnist võib sulle abiks olla reegel, et sama alusega astmete korrutamisel astendajad liidetakse, astmete alus ei muutu.
- Universumi teadaolev vanus on {$ 13 \times 10^{9} $} aastat.
Ülesanne 3
Koosta uus funktsioon Fibbonacci arvu leidmiseks, mis ei kasuta rekursiooni, vaid vaatab for-tsükliga läbi kõik eelnevad Fibbonacci arvud ühe korra. See funktsioon peaks leidma {$ F_{1000} $} kõigest hetkega.
- Uue Fibbonacci arvu leidmiseks on sul on vaja korraga meelespidada ainult eelmist ja üleelmist Fibonacci arvu. Defineeri nende jaoks kaks muutujat.
- Tsükli sees tuleb üleelmise arvu muutuja väärtustada eelmise Fibonacci arvuga ning arvutada uus väärtus eelmisele Fibonacci arvule.
- Kui sa kasutad mõnda tüübitud programmeerimiskeelt, näiteks Javat, siis tavalise long tüübi sisse nii suured arvud ei mahu. Seega pead Javas kasutama näiteks BigInteger teeki.
Lisaülesanded
- Kui palju aega kulub ülesandes 2 nimetatud superarvutil {$ 1000! $} arvutamiseks?
- Koosta programm, mis leiab täpselt, kui palju tehteid ülesandes 1 koostatud rekursiivse Fibbonacci arvu leidmise algoritm teeb. Et tulemus oleks täpne, ära kasuta ülesandes 2 toodud valemit. Sinu algoritm võib kasutada sarnast rekursiooni, katseta seda aga ainult väikeste sisendite korral, 20st suuremate sisendite korral võib see olla liiga aeglane.
- Millise Fibonacci arvu leidmiseks kulub ülesandes 2 toodud superarvutil umbes aasta? Kui eelnevalt toodud valemist on n-i avaldamine on liiga keeruline, siis võid koostada ka programmi, mis proovib valemit erinevate sisenditega, kuni leiab sobiva.
Järgmises peatükis vaatame, kuidas võrrelda omavahel väga erinevate algoritmide kiiruseid, kui nende täpset tööaega on keeruline hinnata.
| << 1.2 Rekursiivsed algoritmid | Sisukord | 1.4 Algoritmi keerukus >> |