Fibonačijeva tehnika pretrage
 | Ovaj članak je započet ili proširen kroz projekat seminarskih radova. Potrebno je proveriti prevod, pravopis i viki-sintaksu. Kada završite sa proverom, dopišete da nakon |provereno=. |
U računarstvu, Fibonačijeva tehnika pretrage je metoda za pretragu sortiranog niza korišćenjem strategije "zavadi,pa vladaj" (engl. divide and conquer) koja sužava prostor pretrage korišćenjem Fibonačijevih brojeva. U poređenju sa binarnom pretragom, Fibonačijeva pretraga ispituje lokacije čije adrese imaju manju disperziju. Stoga, vreme pristupa elementu zavisi od lokacije poslednjeg elementa kom je pristupano. Fibonačijeva tehnika pretrage je u prednosti u odnosu na binarnu pretragu,jer blago smanjuje prosečno vreme potrebno za pristup memorijskoj lokaciji(ako se elementi čuvaju na mediju koji nema jednoobrazni pristup svim elementima,npr. magnetna traka). Napomena,čak ni CPU cache ni RAM memorija nemaju jednoobrazni pristup svim elementima. Vremenska složenost Fibonačijeve pretrage je O(log(n)).
Algoritam
[uredi | uredi izvor]Neka je k član niza F,gde je F niz Fibonačijevih brojeva. Neka je n=Fm dužina niza. Ako dužina niza nije jednaka ni jednom Fibonačijevom broju,onda za dužinu niza uzeti najmanji Fm t.d. je veći od stvarne dužine niza.
Niz Fibonačijevih brojeva se definiše rekurentnom relacijom Fk+2 = Fk+1 + Fk ,za k ≥ 0, F0=0, F1=1.
Da bismo testirali da li element e u listi sortiranih brojeva,primenimo sledeći postupak:
- Postavimo k=m.
- Ako je k nula,prekidamo. Prazan niz.
- Uporedimo element e sa Fk-1
- Ako su jednaki,zaustavimo se.
- Ako je manji od Fk,odbacimo elemente od Fk+1 do n. Postavimo k=k-1 i vratimo se na korak 2.
- Ako je veći od Fk,odbacimo elemente od 1 do Fk-1. Prenumeriše preostale elemente od 1 do Fk. Postavimo k=k-2 i vratimo se na korak 2.
Data je tabela sa zapisima R1,R2,...,RN čiji ključevi su u rastućem poretku K1 < K2 < ... < KN. Algoritam za pronalaženje datog argumenta K je:
Pretpostavimo N+1 = Fk+1.
Korak 1: [inicijalizacija] i<- Fk, p<- Fk-1, q<- Fk-2
Korak 2: [upoređivanje] Ako je K < Ki,pređi na Korak 3. Ako je K > Ki,pređi na Korak 4. Ako je K= Ki,algoritam se uspešno završava.
Korak 3: [umanjivanje i] Ako je q=0,algoritam s neuspešno završava. Inače, (i,p,q) -> (i-q,q,p-q). Preći na Korak 2.
Korak 4: [uvećanje i] Ako je p=1,algoritam s neuspešno završava. Inače, (i,p,q) -> (i+p,p-q,2q-p). Preći na Korak 2.