Valintalajittelualgoritmin analyysi
Valintalajitteluohjelman neliöllinen suoritusaika olisi voitu ennustaa myös suoraan käytettyä algoritmia analysoimalla.
Algoritmi aiempaa täsmällisemmässä ”pseudokoodimuodossa”:
1. toista i:n arvoilla 1..n-1:
2. imin ¬ i
3. toista j:n arvoilla i+1 .. n:
4. jos A[j] < A[imin], niin imin ¬ j
5. vaihda alkiot A[i] ja A[imin] keskenään.
Jos oletetaan, että kunkin ”alkeisoperaation” suoritusaika on 1 aikayksikkö, niin kullakin i:n arvolla (i = 1 .. n-1) on:
- rivin 2 suoritusaika 1 yksikkö
- rivien 3-4 suoritusaika n-i yksikköä
- rivin 5 suoritusaika 1 yksikkö
Kaikkiaan algoritmin suoritusaika n alkion syötetaulukolla saadaan tästä summaamalla yli kaikkien i:n arvojen:
time(n) = åin= 1 ((n-i)+2) = 1/2n2 + 3/2n - 2