تکنیک جستجوی فیبوناچی
در علوم رایانه، تکنیک جستجوی فیبوناچی یک راهی برای جستجو در آرایه مرتب‌شده با استفاده ار الگوریتم تقسیم و غلبه است که قسمتی که قرار است بررسی شود را با کمک اعداد فیبوناچی محدود می‌کند. در مقایسه با جستجوی دودویی، جستجوی فیبوناچی بخش‌هایی را مورد بررسی قرار می‌دهد که مقادیر انها به هم نزدیکتر است و پراکندگی کمتری دارند. وقتی یک عنصر جستجو می‌شود دسترسی غیر یکنواختی به حافظه دارد (یعنی زمان مورد نیاز برای دسترسی به فضای حافظه متغیر است و بستگی به مکانی دارد که مرحله قبل به آن دسترسی پیدا کرده).
مزیت جستجو فیبوناچی نسبت به جستجوی دودویی در کاهش زمان متوسط مورد نیاز برای دسترسی به حافظه است. نوار مغناطیسی نمونه‌ای از مثال دسترسی غیر یکنواخت به حافظه‌است، زمان برای دسترسی به یک عنصر خاص بستگی به فاصلهٔ ان تا عنصری دارد که هم‌اکنون زیر هد نوار است. توجه کنید که آرایه‌های بزرگ که درکش پردازنده یا حتی حافظهٔ اصلی جا نمی‌شوند هم می‌توانند به عنوان یک مثال از دسترسی غیر یکنواخت باشند. جستجوی فیبوناچی دارای پیچیدگی زمانی ((o(log(x است.
جستجوی فیبوناچی در ابتدا توسط کیفر (kiefer) به عنوان روشی برای کم کردن خطاها (مینی‌ماکس) در جستجو برای پیدا کردن بیشینه و کمینه در تابع با یک مد اختراع شد.
الگوریتم[ویرایش]
K به عنوان یک عنصر از F که F یک آرایه از اعداد فیبوناچی است در نظر می‌گیریم. n=Fm اندازهٔ ارایه‌است. اگر اندازهٔ آرایه عدد فیبوناچی نبود، Fm را کوچکترین عدد در F که بزرگتر از n است در نظر می‌گیریم.
آرایه اعداد فیبوناچی زمانی که k ≥ 0, F۱ = 1, F۰ = 0 باشد به صورت Fk+2 = Fk+1 + Fk می‌شود.
برای آزمایش اینکه یک عنصر در لیست اعداد فیبوناچی است مراحل زیر را انجام می‌دهیم.
۱ k = m
۲ اگر k = ۰، توقف. هیچ شباهتی وجود ندارد و عنصر در ارائه نیست.
۳ عنصر را با عنصر Fk−1 مقایسه کنید.
۴ اگر مساوی بود، توقف.
۵ اگر عنصر کمتر از مقدار Fk−1 بود، عناصر محل Fk−1 + 1 تا n را دور می‌اندازیم. k = k − 1 قرار می‌دهیم و به مرحلهٔ دو باز می‌گردیم.
۶ اگر عنصر بزرگتر از مقدار Fk−1 بود، عناصر محل ۱ تا Fk−1 را دور می‌اندازیم. عناصر باقی‌مانده را دوباره از ۱ تا Fk−2 شماره‌گذاری می‌کنیم، k = k − 2 قرار می‌دهیم و به مرحلهٔ دو باز می‌گردیم.
منابع[ویرایش]
- J. Kiefer, "Sequential minimax search for a maximum", Froc. American Mathematical Society, 1953.
- David E. Ferguson, "Fibonaccian searching", Communications of the ACM, vol. 3 , is. 12, p. 648, Dec. 1960.
- Manolis Lourakis, "Fibonaccian search in C". [۱]. Retrieved January 18, 2007. Implements Ferguson's algorithm.
- Donald E. Knuth, "The Art of Computer Programming (second edition)", vol. 3 , p. 418, Nov. 2003.