फाइबोनैचि खोज तकनीक
कंप्यूटर विज्ञान में, फाइबोनैचि खोज तकनीक एक विभाजन और जीत एल्गोरिदम का उपयोग करके क्रमबद्ध सरणी को खोजने की एक विधि है जो फाइबोनैचि संख्याओं की सहायता से संभावित स्थानों को सीमित करती है।[1] बाइनरी खोज एल्गोरिदम की तुलना में जहां क्रमबद्ध सरणी को दो समान आकार के भागों में विभाजित किया जाता है, जिनमें से एक की आगे जांच की जाती है, फाइबोनैचि खोज सरणी को दो भागों में विभाजित करती है जिनके आकार लगातार फाइबोनैचि संख्या होते हैं। औसतन, इससे लगभग 4% अधिक तुलनाएँ क्रियान्वित की जाती हैं,[2] लेकिन इसका फायदा यह है कि किसी को एक्सेस किए गए सरणी तत्वों के सूचकांकों की गणना करने के लिए केवल जोड़ और घटाव की आवश्यकता होती है, जबकि चिरसम्मत बाइनरी खोज के लिए बिट-शिफ्ट (बिटवाइज़ ऑपरेशन देखें), विभाजन या गुणा की आवश्यकता होती है।[1]फाइबोनैचि खोज के पहली बार प्रकाशित होने के समय जो ऑपरेशन साधारण थे फाइबोनैचि खोज में O(लॉग n) की औसत और सबसे खराब स्थिति वाली जटिलता है (बिग O अंकन देखें)।
फाइबोनैचि अनुक्रम में यह गुण होता है कि एक संख्या अपने दो पूर्ववर्तियों का योग होती है। इसलिए अनुक्रम की गणना बार-बार जोड़कर की जा सकती है। दो लगातार संख्याओं का अनुपात स्वर्णिम अनुपात, 1.618 के निकट पहुंचता है... बाइनरी खोज खोज क्षेत्र को समान भागों (1:1) में विभाजित करके काम करती है। फाइबोनैचि खोज सरल ऑपरेशनों का उपयोग करते हुए इसे 1:1.618 तक पहुंचने वाले भागों में विभाजित कर सकती है।
यदि खोजे जा रहे तत्वों में गैर-समान एक्सेस मेमोरी स्टोरेज है (यानी, स्टोरेज स्थान तक पहुंचने के लिए आवश्यक समय एक्सेस किए गए स्थान के आधार पर भिन्न होता है), तो फाइबोनैचि खोज को एक्सेस करने के लिए आवश्यक औसत समय को थोड़ा कम करने में बाइनरी खोज पर लाभ हो सकता है भंडारण स्थान को एक्सेस करने के लिएl यदि खोज निष्पादित करने वाली मशीन में सीधे मैप किया गया सीपीयू कैश है, तो बाइनरी खोज से अधिक कैश मिस हो सकता है क्योंकि जिन तत्वों तक पहुंच होती है वे प्रायः केवल कुछ कैश लाइनों में एकत्रित होते हैं; इसे सरणी को ऐसे भागों में विभाजित करके कम किया जाता है जिनमें दो की शक्तियाँ नहीं होती हैं। यदि डेटा को चुंबकीय टेप डेटा स्टोरेज पर संग्रहीत किया जाता है, जहां खोज समय वर्तमान प्रमुख स्थिति पर निर्भर करता है, तो लंबे समय तक खोज समय और अधिक तुलनाओं के बीच एक ट्रेडऑफ सर्च एल्गोरिदम उत्पन्न होता है जो फाइबोनैचि खोज के समान ही तिरछा (स्क्यूड) है।
फाइबोनैचि खोज स्वर्ण खंड खोज से ली गई है, जो एक अंतराल में यूनिमॉडल फलन के अधिकतम या न्यूनतम की खोज के लिए जैक किफ़र (सांख्यिकीविद्) (1953) द्वारा एल्गोरिदम है।[3]
एल्गोरिदम
मान लीजिए कि k को फाइबोनैचि संख्याओं की सारणी F में एक तत्व के रूप में परिभाषित किया गया है। n = Fm सरणी का आकार है. यदि n एक फाइबोनैचि संख्या नहीं है, तो मान लीजिए Fm में वह सबसे छोटी संख्या F हो जो n से बड़ी हो।
फाइबोनैचि संख्याओं की सारणी को परिभाषित किया गया है जहां Fk+2 = Fk+1+ Fk, जब k ≥ 0, F1 = 1, और F0= 1.
यह जांचने के लिए कि कोई आइटम क्रमित संख्याओं की सूची में है या नहीं, इन चरणों का पालन करें:
- समुच्चय k = m.
- यदि k = 0 है, तो रुकें। कोई मेल नहीं है; आइटम सरणी में नहीं है.
- Fk−1 में तत्व के साथ आइटम की तुलना करें.
- यदि आइटम मेल खाता है, तो रुकें।
- यदि आइटम प्रविष्टि Fk−1 से कम है, स्थिति Fk−1+ 1 से तत्वों को हटा दें से n. k = k −1 समुच्चय करें और चरण 2 पर वापस लौटें।
- यदि आइटम प्रविष्टि Fk−1 से बड़ा है, स्थिति 1 से Fk−1 तक के तत्वों को हटा दें. शेष तत्वों को 1 से Fk−2 तक पुनः क्रमांकित करें, k = k − 2 समुच्चय करें, और चरण 2 पर वापस लौटें।
वैकल्पिक कार्यान्वयन (नुथ द्वारा सॉर्टिंग और सर्चिंग से)।[4]):
अभिलेखों की एक तालिका दी गई R1, R2, ..., RN जिनकी कुंजियाँ बढ़ते क्रम में हैं K1< K2< ... < KN, एल्गोरिथम किसी दिए गए तर्क K की खोज करता है। मान लें N+1 = Fk+1
चरण 1. [आरंभ करें] i ← Fk, p ← Fk-1, q← Fk-2 (पूरे एल्गोरिथम में, p और q लगातार फाइबोनैचि संख्याएं होंगी)
'चरण दो।' [तुलना करें] यदि K < Ki, चरण 3 पर जाएँ; यदि K > Ki चरण 4 पर जाएँ; और यदि K = Ki, एल्गोरिथम सफलतापूर्वक समाप्त हो जाता है।
'चरण 3।' [ घटना i] यदि q=0, एल्गोरिथ्म असफल रूप से समाप्त हो जाता है। अन्यथा समुच्चय करें (i, p, q) ← (i - q, q, p - q) (जो p और q को फाइबोनैचि अनुक्रम में एक स्थान पीछे ले जाता है); फिर चरण 2 पर वापस लौटें
'चरण 4।' [वृद्धि i] यदि p=1, एल्गोरिथ्म असफल रूप से समाप्त हो जाता है। अन्यथा समुच्चय करें (i,p,q) ← (i + q, p - q, 2q - p) (जो फाइबोनैचि अनुक्रम में p और q को दो स्थान पीछे ले जाता है); और चरण 2 पर वापस लौटें
ऊपर प्रस्तुत एल्गोरिदम के दो प्रकार हमेशा वर्तमान अंतराल को बड़े और छोटे उपअंतराल में विभाजित करते हैं। मूल एल्गोरिथ्म,[1]हालाँकि, चरण 4 में नए अंतराल को छोटे और बड़े उपअंतराल में विभाजित किया जाएगा। इसका फायदा यह है कि नया i पुराने i के निकट है और चुंबकीय टेप पर खोज को तेज करने के लिए अधिक उपयुक्त है।
यह भी देखें
- खोज एल्गोरिदम
संदर्भ
- ↑ 1.0 1.1 1.2 Ferguson, David E. (1960). "फाइबोनैशियन खोज". Communications of the ACM. 3 (12): 648. doi:10.1145/367487.367496. S2CID 7982182. Note that the running time analysis is this article is flawed, as pointed out by Overholt in 1972 (published 1973).
- ↑ Overholt, K. J. (1973). "फाइबोनैचि खोज विधि की दक्षता". BIT Numerical Mathematics. 13 (1): 92–96. doi:10.1007/BF01933527. S2CID 120681132.
- ↑ Kiefer, J. (1953). "अधिकतम के लिए अनुक्रमिक मिनिमैक्स खोज". Proceedings of the American Mathematical Society. 4 (3): 502–506. doi:10.1090/S0002-9939-1953-0055639-3.
- ↑ Knuth, Donald E. (2003). The Art of Computer Programming. Vol. 3 (Second ed.). p. 418.
- Lourakis, Manolis. "Fibonaccian search in C". Retrieved January 18, 2007. Implements the above algorithm (not Ferguson's original one).
