Peat�kk 5  Algoritmide keerukus

5.1  Algoritmi keerukuse m�iste

5.1.1  As�mptootiline keerukus

---

Funktsioon c f(n)	Suhe f(25) / f(5)
c1	1
c2 logn	2
c3  n	5
c4  n logn	10
c5  n2	25
c6  n3	125
c7  2n	1 048 576
c8  3n	3 486 784 401

Table 5.1: Programmi t��aja kasv andmete mahu kasvades

---

---

Keerukus	1 MOPS	10 MOPS	100 MOPS	Vahe
n	1 000 000	10 000 000	100 000 000	10 korda
n2	1 000	~ 3 162	10 000	~ 3 korda
n3	100	~ 215	~ 464	~ 2 korda
2n	~ 20	~ 23	~ 26	~ 3 v�rra
3n	~ 13	~ 15	~ 17	~ 2 v�rra

Table 5.2: T��deldavate andmete mahu kasv arvuti kiiruse kasvades

---

5.1.2  Funktsioonide kasv

---

Joonis 5.1: Funktsioonide v�rdlemine

---

---

Joonis 5.2: (a) f(n) = O(g(n)); (b) f(n) = W(g(n)); (c) f(n) = Q(g(n))

---

5.1.3  Kasvuseoste omadused

1. " c > 0 : c f(n) = Q(f(n))
   see t�hendab, et funktsiooni korrutamine konstandiga ei muuda selle kasvukiirust; erijuhul c = 1 saame f(n) = Q(f(n)), j�relikult on seos Q refleksiivne, t�pselt nagu seos = arvudel; samast j�reldub, et ka seosed O ja W on refleksiivsed, t�pselt nagu seosed � ja � arvudel; erijuhul f(n) = 1 saame c = Q(1), j�relikult on k�igi konstantsete funktsioonide kasvukiirused v�rdsed;
   
   
2. f(n) = O(g(n)) Ù g(n) = O(h(n)) É f(n) = O(h(n))
   f(n) = W(g(n)) Ù g(n) = W(h(n)) É f(n) = W(h(n))
   see t�hendab, et seosed O ja W on transitiivsed, t�pselt nagu seosed � ja � arvudel; sellest j�reldub, et ka seos Q on transitiivne, t�pselt nagu seos = arvudel;
   
   
3. f(n) = Q(h(n)) Ù g(n) = O(h(n)) É (f(n) + g(n)) = Q(h(n))
   kahe funktsiooni summa kasvu m��rab kiirema kasvuga liidetav;
   
   
4. f₁(n) = Q(g₁(n)) Ù f₂(n) = O(g₂(n)) É (f₁(n) f₂(n)) = O(g₁(n) g₂(n))
   f₁(n) = Q(g₁(n)) Ù f₂(n) = W(g₂(n)) É (f₁(n) f₂(n)) = W(g₁(n) g₂(n))
   seda omadust v�ib t�lgendada nii, et kahe funktsiooni korrutise kasv on tegurite kasvude korrutis;
   
   
5. kui p(n) on k. astme pol�noom, siis p(n) = Q(n^k)
   see t�hendab, et pol�noomi kasvu m��rab selle k�rgeima astmega liige; v�ga kasulik omadus, mille p�hjal v�ime mistahes pol�noomi uurimise asendada �ksliikme uurimisega;
   
   
6. " 0 � r � s : n^r = O(n^s)
   see t�hendab, et madalama astmega astmefunktsioon ei kasva kiiremini k�rgema astmega astmefunktsioonist; kehtib ka tugevam v�ide: madalama astmega funktsioon kasvab alati rangelt aeglasemalt;
   
   
7. " k � 0, b > 1 : n^k = O(bⁿ)
   see t�hendab, et mitte �kski astmefunktsioon ei kasva kiiremini �hestki eksponentfunktsioonist; tegelikult kasvab astmefunktsioon alati rangelt aeglasemalt;
   
   
8. " k > 0, b > 1 : log_b n = O(n^k)
   see t�hendab, et �kski logaritmfunktsioon ei kasva kiiremini �hestki astmefunktsioonist; tegelikult kasvab logaritmfunktsioon alati rangelt aeglasemalt;
   
   
9. " b₁ > 1, b₂ > 1 : log_b1 n = Q(log_b2 n)
   see t�hendab, et k�ik logaritmfunktsioonid kasvavad sama kiirusega;
   
   
10. " r � 0 : �_{i = 1}ⁿ i^r = Q(n^{r + 1})
    see t�hendab, et r. j�rku astmerea summa kasvab nagu (r+1). astme pol�noom.

5.2  Algoritmide keerukuse hindamine

5.2.1  Maksumuse mudel

5.2.2  Lineaarne algoritm

k�sk-1
k�sk-2
...
k�sk-k

5.2.3  Hargnemistega algoritm

kui tingimus
    t�ene-k�sud
muidu
    v��r-k�sud
l�ppkui

--- n, k � N; n � k > 0
kui n / k � N
    --- midagi, mis on Q(n)
muidu
    --- midagi, mis on Q(1)
l�ppkui

• parimal juhul:
  T_min(N) = Q(1) + min(Q(n), Q(1)) = Q(1) + Q(1) = Q(1);
  
  
• halvimal juhul:
  T_max(n) = Q(1) + max(Q(n), Q(1)) = Q(1) + Q(n) = Q(n);
  
  
• keskmiselt:
  kui arvudele n ja k pole seatud muid piiranguid, on jaguvuse t�en�osus 1 / k, mis annab keskmiseks ajakuluks
  T(n) = Q(1) + (1 / k) Q(n) + (1 - 1 / k) Q(1) = Q(n / k),
  sest pole raske n�ha, et n � k korral on T(n) avaldises domineeriv keskmine liidetav.

5.2.4  Iteratiivne algoritm

korda i�1 ... k
    k�sud
l�ppkorda

--- a_{1 ... n} --- summeeritav jada
s�0
korda i�1 ... n
    s�s + a_i
l�ppkorda
v�ljasta s

--- a_{1 ... n} --- uuritav jada
k�0
korda i�1 ... n
    korda j�i + 1 ... n
       kui a_i > a_j
          k�k + 1
       l�ppkui
    l�ppkorda
l�ppkorda
v�ljasta k

5.2.5  Rekursiivne algoritm

--- n � N
kui n = 0
    tagasta 1
muidu
    --- rekursioon
    tagasta n * (n - 1)!
l�ppkui

---

T(n) avaldis	lahend
T(n / c1) + Q(1)	Q(logn)
T(n - 1) + Q(1)	Q(n)
c2 T(n / c2) + Q(1)	Q(n)
c3 T(n / c3) + Q(n)	Q(n logn)
T(n - 1) + Q(n)	Q(n2)
c4 T(n - 1) + Q(1)	Q(c4n)

Table 5.3: M�nede sageli esinevate rekurrentsete v�rrandite lahendid

---

5.3  Praktiline n�uanne

�lesanded

Kirjandus

J�ri Kiho. Algoritmid ja andmestruktuurid. Tartu �likool, 2003.

Andmestruktuuride realiseerimist ja klassikalisi algoritme k�sitlev �pik, milles leidub ka keerukuse p�him�istetele p�hendatud peat�kk. 148 lk.

Valdo Praust. Keerukusteooria alused. �likoolide Informaatikakeskus, 1996.

Algoritmide ja �lesannete keerukuse teoreetilisemale poolele keskenduv �pik. 212 lk.

Thomas H. Cormen, Clifford Stein, Charles Leiserson, Ronald Rivest. Introduction to Algorithms. MIT, 2001.

Eelmise tr�kiga klassikaks saanud algoritmide ja andmestruktuuride p�hi�pik, mis annab �sna hea �levaate ka algoritmide keerukuse hindamisest ja selleks vajalikust matemaatilisest aparatuurist. 1180 lk.

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест. Алгоритмы: построение и анализ. МЦНМО, 2001.

Eelmise t�lge. 960 lk.

Herbert S. Wilf. Algorithms and Complexity. Prentice Hall, 1986.

�likooli keskmiste kursuste tasemele orienteeritud konspekt. 240 lk.
http://www.cis.upenn.edu/~wilf/AlgComp2.html

1

Eksponentfunktsiooniks nimetatakse funktsiooni kujul a^x, kus a on konstant ja x funktsiooni argument. Mitte segi ajada astmefunktsiooniga, mis avaldub kujul x^a.

2

Astmefunktsioonid on pol�noomide lihtsamad erijuhud.

3

See ju ongi funktsioonide m�te!

4

Siin ja edaspidi m�rgime t�en�osusi mitte protsentides, vaid reaalarvudega 0 ... 1. Arvestades, et protsent t�hendab sajandikku, saame 20% = 20 / 100 = 0,2. Vahe on selles, et viimast kuju kasutades ei pea valemites t�en�osusi sajaga jagama, mis muudab valemid veidi lihtsamaks ja �levaatlikumaks.