Izpitno vprašanje RAČ2PRA 14500

Iz MaFiRaWiki


Predmet Računalništvo 2 (FMF PRA)

Vsebina

Vprašanje

Razloži, kako z bisekcijo poiščeš element v urejeni tabeli števil. Analiziraj časovno zahtevnost metode.

Odgovor

Razlaga

Denimo, da imamo urejeno tabelo podatkov

a[0], a[1], ..., a[n] , kjer velja: a[n] >= a[n+1]

in da v njen iščemo podatek x.

V prvem koraku še ne vemo kateri element je x, zato je iskalno območje celotna tabela

a[0], a[1], ..., a[n]

Primerjajmo x z elementom a[n/2], ki je na sredini iskalnega območja.

Imamo tri možnosti:

če je a[n/2] == x, smo podatek x našli,

če je a[n/2] > x, potem je x v drugi polovici tabele, zato iskalno območje skrčimo na

a[n/2+1], a[n/2+2], ..., a[n]

in ponovimo postopek na tem območju.

Če je a[n/2] < x, potem je x v prvi polovici tabele, zato iskalno območje skrčimo na

a[0], a[1], ..., a[n/2-1]

in ponovimo postopek na tem območju.

Časovna zahtevnost

Recimo, da rešujemo problem z n elemnti.

  • Po prevem primerjanju imamo n/2 elemntov
  • Po drugem imamo n/4 elemntov
  • ....
  • Po i tem primerjanju imam n/2i elementov

Iz tega sledi, da nam ostane 1 element tedaj ko je n = 2i

Od tu dobimo i = log(n) in stem časovno zahtevnost O(log(n))

Osebna orodja