Фибоначијева техника претраге
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
У рачунарству, Фибоначијева техника претраге је метода за претрагу сортираног низа коришћењем стратегије "завади,па владај" (енгл. divide and conquer) која сужава простор претраге коришћењем Фибоначијевих бројева. У поређењу са бинарном претрагом, Фибоначијева претрага испитује локације чије адресе имају мању дисперзију. Стога, време приступа елементу зависи од локације последњег елемента ком је приступано. Фибоначијева техника претраге је у предности у односу на бинарну претрагу,јер благо смањује просечно време потребно за приступ меморијској локацији(ако се елементи чувају на медију који нема једнообразни приступ свим елементима,нпр. магнетна трака). Напомена,чак ни CPU cache ни RAM меморија немају једнообразни приступ свим елементима. Временска сложеност Фибоначијеве претраге је O(log(n)).
Алгоритам
[уреди | уреди извор]Нека је k члан низа F,где је F низ Фибоначијевих бројева. Нека је n=Fm дужина низа. Ако дужина низа није једнака ни једном Фибоначијевом броју,онда за дужину низа узети најмањи Fm т.д. је већи од стварне дужине низа.
Низ Фибоначијевих бројева се дефинише рекурентном релацијом Fk+2 = Fk+1 + Fk ,за k ≥ 0, F0=0, F1=1.
Да бисмо тестирали да ли елемент e у листи сортираних бројева,применимо следећи поступак:
- Поставимо k=m.
- Ако је k нула,прекидамо. Празан низ.
- Упоредимо елемент e са Fk-1
- Ако су једнаки,зауставимо се.
- Ако је мањи од Fk,одбацимо елементе од Fk+1 до n. Поставимо k=k-1 и вратимо се на корак 2.
- Ако је већи од Fk,одбацимо елементе од 1 до Fk-1. Пренумерише преостале елементе од 1 до Fk. Поставимо k=k-2 и вратимо се на корак 2.
Дата је табела са записима R1,R2,...,RN чији кључеви су у растућем поретку K1 < K2 < ... < KN. Алгоритам за проналажење датог аргумента K je:
Претпоставимо N+1 = Fk+1.
Корак 1: [иницијализација] i<- Fk, p<- Fk-1, q<- Fk-2
Корак 2: [упоређивање] Ако је K < Ki,пређи на Корак 3. Ако је K > Ki,пређи на Корак 4. Ако је K= Ki,алгоритам се успешно завршава.
Корак 3: [умањивање i] Ако је q=0,алгоритам с неуспешно завршава. Иначе, (i,p,q) -> (i-q,q,p-q). Прећи на Корак 2.
Корак 4: [увећање i] Ако је p=1,алгоритам с неуспешно завршава. Иначе, (i,p,q) -> (i+p,p-q,2q-p). Прећи на Корак 2.