Tölvumál - 01.10.1986, Qupperneq 17

talnanna í B, svo að við verðum að gæta þess að vinna
með afrit af hinum upprunalega vektor.
Það er hægt að líta á þennan algóritma sem
útsláttarkeppni þar sem hver umferð er spiluð
samtímis og hver tala í B er lið í keppninni. í
upphafi höfum við n(=2k ) lið. í annari umferð hefur
helmingurinn af liðunum verið sleginn út, svo að við
höfum n/2 )lið. í þriðju umferð leika n/4 (=2^7*
lið o.s.frv. Þegar kemur að úrslitaleiknum þá höfum
við 2(=2X) lið. Þar sem allir leikir í hverri umferð
eru spilaðir samtímis er timinn sem allt mótið tekur
i réttu hlutfalli við fjölda umferða. Fjöldi umferða
er K, sem er 2-logaritminn af n. Lítum nú aftur á
dæmið að ofan með þessari túlkun.
9
Ef til dæmis n=8 og k=3, höfum við 3 umferðir. Þá eru
8 tölur í vektornum og nota þarf 4 undirtölvur.
í þessum algóritma fáum við ekki hraðaukningu, sem er
i réttu hlutfalli við fjölda undirtölva sem við
notum. Fjöldi undirtölva er af stærðargráðunni n, en
timinn, sem hann tekur er af stærðargráðunni log (n).
Þetta þ/ðir að hann er aðeins n/log(n) sinnum hraðari
en runu algóritminn, en fjöldi undirtölva er samt af
stærðargráðunni n.
17