घातीय खोज: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 11: Line 11:
}}
}}


[[कंप्यूटर विज्ञान]] में,   घातीय खोज (जिसे दोहरीकरण खोज या सरपट खोज या स्ट्रुज़िक खोज भी कहा जाता है)<ref name=Baeza-Yates/> [[कलन विधि]] है, जो [[जॉन बेंटले (कंप्यूटर वैज्ञानिक)]] और [[एंड्रयू ची-चिह याओ]] द्वारा 1976 में क्रमबद्ध, असीमित/अनंत सूचियों की खोज के लिए बनाया गया था।<ref name=PaperBentley/>इसे लागू करने के कई तरीके हैं, जिनमें से सबसे आम है उस सीमा को निर्धारित करना जिसमें खोज कुंजी स्थित है और उस सीमा के भीतर  बाइनरी खोज करना है। यह बिग-ओ नोटेशन (लॉग i) लेता है जहां i सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है सूची।
[[कंप्यूटर विज्ञान]] में, '''घातांकीय खोज''' (जिसे दोहरीकरण खोज या तीव्र खोज या स्ट्रुज़िक खोज भी कहा जाता है) <ref name=Baeza-Yates/> यह [[कलन विधि|एल्गोरिथम]] है, जो [[जॉन बेंटले (कंप्यूटर वैज्ञानिक)]] और [[एंड्रयू ची-चिह याओ]] द्वारा 1976 में क्रमबद्ध किया था, इस प्रकार से यह असीमित/अनंत सूचियों की खोज के लिए बनाया गया था। <ref name=PaperBentley/> इसे प्रयुक्त करने के अनेक विधि होती हैं, जिनमें से यह सबसे समान होते है | यह उस सीमा को निर्धारित करना हैं जिसमें खोज कुंजी स्थित होती है और उस सीमा के अन्दर बाइनरी खोज करना होता है। यह ''O''(log ''i'') प्राप्त करता है जहां ''i'' सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है


घातीय खोज का उपयोग बंधी हुई सूचियों में खोजने के लिए भी किया जा सकता है। घातीय खोज बाउंडेड सूचियों के लिए अधिक पारंपरिक खोजों से भी बेहतर प्रदर्शन कर सकती है, जैसे कि बाइनरी खोज, जब खोजा जा रहा तत्व सरणी की शुरुआत के करीब होता है। ऐसा इसलिए है क्योंकि घातीय खोज O(log i) समय में चलेगी, जहां i सूची में खोजे जा रहे तत्व का सूचकांक है, जबकि बाइनरी खोज O(log n) समय में चलेगी, जहां n तत्वों की संख्या है सूची में।
इस प्रकार से घातांकीय खोज का उपयोग बंधी हुई सूचियों में खोजने के लिए भी किया जा सकता है। घातांकीय खोज बाउंडेड सूचियों के लिए अधिक पारंपरिक खोजों से भी श्रेष्ठ प्रदर्शन कर सकती है, जैसे कि बाइनरी खोज, जब खोजी जा रही अवयव सरणी के प्रारंभ में समीप होता है। किन्तु ऐसा इसलिए है क्योंकि घातांकीय खोज O(log i) समय में चलेगी, जहां i सूची में खोजे जा रहे अवयव का सूचकांक होता है, जबकि बाइनरी खोज O(log n) समय में चलेगी, जहां n अवयवों की सूची में संख्या है


== एल्गोरिथम ==
== एल्गोरिथम ==


घातीय खोज   निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण होते हैं. पहला चरण   सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होगी। दूसरे चरण में, इस श्रेणी पर   बाइनरी खोज की जाती है। पहले चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम पहले [[घातांक]], जे की तलाश करता है, जहां मान 2 है{{sup|j}} खोज कुंजी से बड़ा है. यह मान, 2{{sup|j}} 2, 2 की पिछली शक्ति के साथ बाइनरी खोज के लिए ऊपरी सीमा बन जाता है{{sup|j - 1}}, बाइनरी खोज के लिए निचली सीमा है।<ref name="NotesJonsson"/>
किन्तु घातांकीय खोज निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण प्रमुख होते हैं. प्रथम चरण सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होती है । दूसरे चरण में, इस श्रेणी पर बाइनरी खोज की जाती है। प्रथम चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम प्रथम [[घातांक]], ''j'', की खोज करता है, जहां मान 2{{sup|j}} होता है | यह खोज कुंजी से अधिक होता है | यह मान, 2{{sup|j}} 2, की पूर्व शक्ति के साथ बाइनरी खोज के लिए ऊपरी सीमा बन जाता है | और 2{{sup|j - 1}}, बाइनरी खोज के लिए निचली सीमा होती है। <ref name="NotesJonsson"/>


<syntaxhighlight lang="cpp">
<syntaxhighlight lang="cpp">
Line 36: Line 36:
}
}
</syntaxhighlight>
</syntaxhighlight>
प्रत्येक चरण में, एल्गोरिदम वर्तमान खोज सूचकांक में खोज कुंजी मान की तुलना कुंजी मान से करता है। यदि वर्तमान सूचकांक पर तत्व खोज कुंजी से छोटा है, तो एल्गोरिदम दोहराता है, इसे दोगुना करके अगले खोज सूचकांक पर जाता है, 2 की अगली शक्ति की गणना करता है।<ref name="NotesJonsson"/>यदि वर्तमान सूचकांक में तत्व खोज कुंजी से बड़ा है, तो एल्गोरिदम अब जानता है कि खोज कुंजी, यदि यह सूची में बिल्कुल भी शामिल है, तो पिछले खोज सूचकांक द्वारा गठित अंतराल में स्थित है, 2{{sup|j - 1}}, और वर्तमान खोज सूचकांक, 2{{sup|j}}. यदि खोज कुंजी सूची में नहीं है, या सूची में खोज कुंजी की स्थिति है, तो बाइनरी खोज या तो किसी विफलता के परिणाम के साथ की जाती है।
प्रत्येक चरण में, एल्गोरिदम वर्तमान खोज सूचकांक में खोज कुंजी मान की तुलना कुंजी मान से करता है। यदि वर्तमान सूचकांक पर अवयव खोज कुंजी से लघु है, तब एल्गोरिदम दोहराता है, इसे दोगुना करके अगले खोज सूचकांक पर जाता है, 2 की अगली शक्ति की गणना करता है। <ref name="NotesJonsson"/> यदि वर्तमान सूचकांक में अवयव खोज कुंजी से अधिक है, तब एल्गोरिदम जानता है कि खोज कुंजी, यदि सूची में बिल्कुल भी सम्मिलित है, तब यह पिछले खोज सूचकांक 2{{sup|j - 1}}, द्वारा गठित अंतराल में स्थित होते है, और वर्तमान खोज सूचकांक 2{{sup|j}} यदि खोज कुंजी सूची में नहीं होते है,इस सूची में खोज कुंजी की स्थित है, तब बाइनरी खोज यह तब किसी विफलता के परिणाम के साथ की जाती है।


== प्रदर्शन ==
== प्रदर्शन ==


एल्गोरिदम के पहले चरण में O(लॉग i) समय लगता है, जहां i वह सूचकांक है जहां सूची में खोज कुंजी होगी। ऐसा इसलिए है, क्योंकि बाइनरी खोज के लिए ऊपरी सीमा निर्धारित करने में, जबकि लूप बिल्कुल निष्पादित होता है <math>\lceil \log(i) \rceil</math> बार. चूंकि सूची को खोज सूचकांक को दोगुना करने के बाद क्रमबद्ध किया गया है <math>\lceil \log(i) \rceil</math> कई बार, एल्गोरिथ्म   खोज सूचकांक पर होगा जो कि i से अधिक या उसके बराबर है <math>2^{\lceil \log(i) \rceil} \ge i</math>. इस प्रकार, एल्गोरिथम के पहले चरण में O(log i) समय लगता है।
एल्गोरिदम के प्रथम चरण में ''O''(log ''i'') समय लगता है, जहां i वह सूचकांक है जहां सूची में खोज कुंजी होती हैं। ऐसा इसलिए है, क्योंकि बाइनरी खोज के लिए ऊपरी सीमा निर्धारित करने में, जबकि लूप बिल्कुल <math>\lceil \log(i) \rceil</math> अनेक बार निष्पादित होता है | चूंकि सूची को खोज सूचकांक को <math>\lceil \log(i) \rceil</math> पश्चात् दोगुना करने के क्रमबद्ध किया गया है अनेक बार, एल्गोरिथ्म खोज सूचकांक पर होता हैं जो कि <math>2^{\lceil \log(i) \rceil} \ge i</math>. से ''i'' अधिक या उसके सामान होता है इस प्रकार, एल्गोरिथम के प्रथम चरण में O(log i) समय लगता है।


एल्गोरिथम का दूसरा भाग भी O(log i) समय लेता है। चूंकि दूसरा चरण केवल   द्विआधारी खोज है, इसमें O(लॉग एन) लिया जाता है जहां n खोजे जा रहे अंतराल का आकार है। इस अंतराल का आकार 2 होगा{{sup|''j''}} - 2{{sup|''j'' - 1}} जहां, जैसा कि ऊपर देखा गया है, j = log i। इसका मतलब है कि खोजे जा रहे अंतराल का आकार 2 है{{sup|log ''i''}} - 2{{sup|log ''i'' - 1}} = 2{{sup|log ''i'' - 1}}. इससे हमें लॉग का रन टाइम मिलता है (2{{sup|log ''i'' - 1}}) = लॉग (i) - 1 = O(लॉग i).
इस प्राकर से एल्गोरिथम का दूसरा भाग भी O(log i) समय लेता है। चूंकि दूसरा चरण केवल द्विआधारी खोज होता है, इसमें ''O''(log ''n'') लिया जाता है | जहां n खोजे जा रहे अंतराल का आकार होते है। इस अंतराल का आकार 2{{sup|''j''}} - 2{{sup|''j'' - 1}} होता हैं | जहां, जैसा कि ऊपर देखा गया है, j = log i। इसका अर्थ है कि खोजे जा रहे अंतराल का आकार 2<sup>log ''i''</sup> - 2<sup>log ''i'' - 1</sup> = 2<sup>log ''i'' - 1</sup> होता है। इससे हमें लॉग का रन टाइम मिलता है (2<sup>log ''i'' - 1</sup>) = log (''i'') - 1 = ''O''(log ''i'').


यह एल्गोरिथम को कुल रनटाइम देता है, जिसकी गणना O(log i) + O(log i) = 2 O(log i) = O(log i) के दो चरणों के रनटाइम को जोड़कर की जाती है।
और यह एल्गोरिथम को कुल रनटाइम देता है, जिसकी गणना ''O''(log ''i'') + ''O''(log ''i'') = 2 ''O''(log ''i'') = ''O''(log ''i'') के दो चरणों के रनटाइम को जोड़कर की जाती है।


== विकल्प ==
== विकल्प ==
बेंटले और याओ ने घातीय खोज के लिए कई विविधताएँ सुझाईं।<ref name="PaperBentley"/>एल्गोरिथम के दूसरे चरण में बाइनरी खोज के लिए ऊपरी सीमा का निर्धारण करते समय, इन विविधताओं में   यूनरी खोज के विपरीत,   बाइनरी खोज करना शामिल होता है। यह एल्गोरिथम के पहले चरण को दो भागों में विभाजित करता है, जिससे एल्गोरिथम कुल मिलाकर तीन-चरण वाला एल्गोरिथम बन जाता है। नया पहला चरण   मान निर्धारित करता है<math>j'</math>, बहुत कुछ पहले जैसा, वैसा <math>2^{j'}</math> खोज कुंजी से बड़ा है और <math>2^{j'/2}</math> खोज कुंजी से कम है. पहले,<math>j'</math>2 की अगली घात की गणना करके (अर्थात, j में 1 जोड़कर) एकात्मक तरीके से निर्धारित किया गया था। प्रकारांतर में यह प्रस्तावित है कि <math>j'</math> इसके बजाय दोगुना कर दिया गया है (उदाहरण के लिए, 2 से कूदकर)।{{sup|2}} से 2{{sup|4}} 2 के विपरीत{{sup|3}}). पहला<math>j'</math>ऐसा है कि <math>2^{j'}</math> खोज कुंजी से अधिक होने पर यह पहले की तुलना में अधिक कठोर ऊपरी सीमा बनाती है।   बार यह<math>j'</math>पाया जाता है, एल्गोरिथ्म अपने दूसरे चरण में चला जाता है और द्वारा गठित अंतराल पर  बाइनरी खोज की जाती है <math>j'/2</math> और <math>j'</math>, अधिक सटीक ऊपरी सीमा घातांक जे दे रहा है। यहां से, एल्गोरिदम का तीसरा चरण अंतराल 2 पर बाइनरी खोज करता है{{sup|''j'' - 1}} और 2{{sup|''j''}}, पहले जैसा। इस विविधता का प्रदर्शन है <math>\lfloor \log i \rfloor + 2 \lfloor \log(\lfloor \log i \rfloor + 1)\rfloor + 1</math> = O(लॉग i).
बेंटले और याओ ने घातांकीय खोज के लिए अनेक विविधताएँ प्रस्तुत की हैं । <ref name="PaperBentley"/> एल्गोरिथम के दूसरे चरण में बाइनरी खोज के लिए ऊपरी सीमा का निर्धारण करते समय, इन विविधताओं में यूनरी खोज के विपरीत, बाइनरी खोज करना सम्मिलित होता है। यह एल्गोरिथम के प्रथम चरण को दो भागों में विभाजित करता है, जिससे एल्गोरिथम कुल मिलाकर तीन-चरण वाला एल्गोरिथम बन जाता है। नया पहला चरण <math>j'</math> मान निर्धारित करता है, तथा इसमें बहुत कुछ पहले जैसा होता हैं, <math>2^{j'}</math> की खोज कुंजी से अधिक होती है और <math>2^{j'/2}</math> खोज कुंजी से कम है. प्रथम ,<math>j'</math>को 2 की अगली घात की गणना करके (अर्थात, 1 को j में जोड़कर) एकात्मक विधि से निर्धारित किया गया था। प्रकारांतर में यह प्रस्तावित है कि इसके अतिरिक्त <math>j'</math> दोगुना कर दिया गया है (उदाहरण के लिए, 2<sup>2</sup> के विपरीत 2<sup>4</sup> से 2<sup>3</sup> पर कूदना) हैं | पहला <math>j'</math> ऐसा है कि <math>2^{j'}</math> खोज कुंजी से अधिक होने पर यह प्रथम की तुलना में अधिक कठोर ऊपरी सीमा बनाती है। जब यह <math>j'</math> पाया जाता है, एल्गोरिथ्म अपने दूसरे चरण में चला जाता है | इसमें <math>j'/2</math> और <math>j'</math> द्वारा गठित अंतराल पर बाइनरी खोज की जाती है, अधिक स्पष्ट ऊपरी सीमा घातांक <math>j'</math> दे रहा है। यहां से, एल्गोरिदम का तीसरा चरण अंतराल 2{{sup|''j'' - 1}} और 2{{sup|''j''}} पर बाइनरी खोज करता है, प्रथम जैसा <math>\lfloor \log i \rfloor + 2 \lfloor \log(\lfloor \log i \rfloor + 1)\rfloor + 1</math> = ''O''(log ''i'') इस विविधता का प्रदर्शन होता है।


बेंटले और याओ इस भिन्नता को सामान्यीकृत करते हैं जहां एल्गोरिथ्म के पहले चरण के दौरान बाइनरी खोजों की कोई भी संख्या, k, निष्पादित की जाती है, जिससे k-नेस्टेड बाइनरी खोज भिन्नता मिलती है। मूल घातीय खोज एल्गोरिदम की तरह, (लॉग i) समय में चलने वाली विविधताओं के लिए एसिम्प्टोटिक रनटाइम नहीं बदलता है।
अतः बेंटले और याओ इस भिन्नता को सामान्यीकृत करते हैं जहां एल्गोरिथ्म के प्रथम चरण के समय बाइनरी खोजों की कोई भी संख्या, k, निष्पादित की जाती है, जिससे k-नेस्टेड बाइनरी खोज भिन्नता मिलती है। मूल घातांकीय खोज एल्गोरिदम की तरह, ''O''(log ''i'') समय में चलने वाली विविधताओं के लिए एसिम्प्टोटिक रनटाइम नहीं परिवर्तित करता है।


इसके अलावा, जब के-नेस्टेड बाइनरी खोज के उपरोक्त परिणाम का उपयोग क्रमबद्ध सरणी पर किया जाता है, तो [[ बिखरा हुआ पेड़ |बिखरा हुआ पेड़]] के   तंग संस्करण के साथ   डेटा संरचना दी जा सकती है।<ref name="PaperAndersson"/>इसका उपयोग करते हुए, खोज के दौरान की गई तुलनाओं की संख्या लॉग (डी) + लॉग लॉग (डी) + ... + (लॉग) है{{sup|*}}d), जहां d एक्सेस किए गए अंतिम तत्व और एक्सेस किए जा रहे वर्तमान तत्व के बीच रैंक का अंतर है।
इसके अतिरिक्त , जब k-नेस्टेड बाइनरी खोज के उपरोक्त परिणाम का उपयोग क्रमबद्ध सरणी पर किया जाता है, तब [[ बिखरा हुआ पेड़ |डायनामिक फिंगर प्रॉपर्टी]] के संक्षेप संस्करण के साथ डेटा संरचना दी जा सकती है।<ref name="PaperAndersson"/> इसका उपयोग करते हुए, खोज के समय की गई तुलनाओं की संख्या log (''d'') + log log (''d'') + ... + ''O''(log <sup>*</sup>''d'') होती हैं, जहां d एक्सेस किए गए अंतिम अवयव और एक्सेस किए जा रहे वर्तमान अवयव के मध्य रैंक का अंतर है । इस प्रकार से यह वर्तमान अवयव तक पहुँचा जाता है।


== अनुप्रयोग ==
== अनुप्रयोग ==
खोज बैंड को तेजी से बढ़ाने पर आधारित   एल्गोरिदम O(ns) के लिए [[अनुक्रम संरेखण]] को हल करता है, जहां n अनुक्रमों की लंबाई है और s उनके बीच की संपादन दूरी है।<ref>{{Cite journal |last=Ukkonen |first=Esko |date=March 1985 |title=स्ट्रिंग्स में अनुमानित पैटर्न ढूँढना|url=http://dx.doi.org/10.1016/0196-6774(85)90023-9 |journal=Journal of Algorithms |volume=6 |issue=1 |pages=132–137 |doi=10.1016/0196-6774(85)90023-9 |issn=0196-6774}}</ref><ref>{{Cite web |last=Šošić |first=Martin |last2=Šikić |first2=Mile |date=2016-08-23 |title=Edlib: a C/C++ library for fast, exact sequence alignment using edit distance |url=http://dx.doi.org/10.1101/070649 |access-date=2023-03-17 |website=dx.doi.org}}</ref>
इस प्रकार से खोज बैंड को तीव्रता से बढ़ाने पर आधारित एल्गोरिदम O(ns) के लिए [[अनुक्रम संरेखण]] का समाधान करता है, जहां n अनुक्रमों की लंबाई है और s उनके मध्य की संपादन दूरी होती है। <ref>{{Cite journal |last=Ukkonen |first=Esko |date=March 1985 |title=स्ट्रिंग्स में अनुमानित पैटर्न ढूँढना|url=http://dx.doi.org/10.1016/0196-6774(85)90023-9 |journal=Journal of Algorithms |volume=6 |issue=1 |pages=132–137 |doi=10.1016/0196-6774(85)90023-9 |issn=0196-6774}}</ref><ref>{{Cite web |last=Šošić |first=Martin |last2=Šikić |first2=Mile |date=2016-08-23 |title=Edlib: a C/C++ library for fast, exact sequence alignment using edit distance |url=http://dx.doi.org/10.1101/070649 |access-date=2023-03-17 |website=dx.doi.org}}</ref>
==यह भी देखें==
==यह भी देखें==
*[[रेखीय खोज]]
*[[रेखीय खोज]]
Line 107: Line 107:
</ref>
</ref>
}}
}}
[[Category: एल्गोरिदम खोजें]]


[[Category: Machine Translated Page]]
[[Category:Created On 25/06/2023]]
[[Category:Created On 25/06/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एल्गोरिदम खोजें]]

Latest revision as of 13:34, 3 August 2023

घातीय खोज
ClassSearch algorithm
Data structureArray
Worst-case performanceO(log i)
Best-case performanceO(1)
Average performanceO(log i)
Worst-case space complexityO(1)

कंप्यूटर विज्ञान में, घातांकीय खोज (जिसे दोहरीकरण खोज या तीव्र खोज या स्ट्रुज़िक खोज भी कहा जाता है) [1] यह एल्गोरिथम है, जो जॉन बेंटले (कंप्यूटर वैज्ञानिक) और एंड्रयू ची-चिह याओ द्वारा 1976 में क्रमबद्ध किया था, इस प्रकार से यह असीमित/अनंत सूचियों की खोज के लिए बनाया गया था। [2] इसे प्रयुक्त करने के अनेक विधि होती हैं, जिनमें से यह सबसे समान होते है | यह उस सीमा को निर्धारित करना हैं जिसमें खोज कुंजी स्थित होती है और उस सीमा के अन्दर बाइनरी खोज करना होता है। यह O(log i) प्राप्त करता है जहां i सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है ।

इस प्रकार से घातांकीय खोज का उपयोग बंधी हुई सूचियों में खोजने के लिए भी किया जा सकता है। घातांकीय खोज बाउंडेड सूचियों के लिए अधिक पारंपरिक खोजों से भी श्रेष्ठ प्रदर्शन कर सकती है, जैसे कि बाइनरी खोज, जब खोजी जा रही अवयव सरणी के प्रारंभ में समीप होता है। किन्तु ऐसा इसलिए है क्योंकि घातांकीय खोज O(log i) समय में चलेगी, जहां i सूची में खोजे जा रहे अवयव का सूचकांक होता है, जबकि बाइनरी खोज O(log n) समय में चलेगी, जहां n अवयवों की सूची में संख्या है ।

एल्गोरिथम

किन्तु घातांकीय खोज निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण प्रमुख होते हैं. प्रथम चरण सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होती है । दूसरे चरण में, इस श्रेणी पर बाइनरी खोज की जाती है। प्रथम चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम प्रथम घातांक, j, की खोज करता है, जहां मान 2j होता है | यह खोज कुंजी से अधिक होता है | यह मान, 2j 2, की पूर्व शक्ति के साथ बाइनरी खोज के लिए ऊपरी सीमा बन जाता है | और 2j - 1, बाइनरी खोज के लिए निचली सीमा होती है। [3]

// Returns the position of key in the array arr of length size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }

    return binary_search(arr, key, bound/2, min(bound + 1, size));
}

प्रत्येक चरण में, एल्गोरिदम वर्तमान खोज सूचकांक में खोज कुंजी मान की तुलना कुंजी मान से करता है। यदि वर्तमान सूचकांक पर अवयव खोज कुंजी से लघु है, तब एल्गोरिदम दोहराता है, इसे दोगुना करके अगले खोज सूचकांक पर जाता है, 2 की अगली शक्ति की गणना करता है। [3] यदि वर्तमान सूचकांक में अवयव खोज कुंजी से अधिक है, तब एल्गोरिदम जानता है कि खोज कुंजी, यदि सूची में बिल्कुल भी सम्मिलित है, तब यह पिछले खोज सूचकांक 2j - 1, द्वारा गठित अंतराल में स्थित होते है, और वर्तमान खोज सूचकांक 2j यदि खोज कुंजी सूची में नहीं होते है,इस सूची में खोज कुंजी की स्थित है, तब बाइनरी खोज यह तब किसी विफलता के परिणाम के साथ की जाती है।

प्रदर्शन

एल्गोरिदम के प्रथम चरण में O(log i) समय लगता है, जहां i वह सूचकांक है जहां सूची में खोज कुंजी होती हैं। ऐसा इसलिए है, क्योंकि बाइनरी खोज के लिए ऊपरी सीमा निर्धारित करने में, जबकि लूप बिल्कुल अनेक बार निष्पादित होता है | चूंकि सूची को खोज सूचकांक को पश्चात् दोगुना करने के क्रमबद्ध किया गया है अनेक बार, एल्गोरिथ्म खोज सूचकांक पर होता हैं जो कि . से i अधिक या उसके सामान होता है इस प्रकार, एल्गोरिथम के प्रथम चरण में O(log i) समय लगता है।

इस प्राकर से एल्गोरिथम का दूसरा भाग भी O(log i) समय लेता है। चूंकि दूसरा चरण केवल द्विआधारी खोज होता है, इसमें O(log n) लिया जाता है | जहां n खोजे जा रहे अंतराल का आकार होते है। इस अंतराल का आकार 2j - 2j - 1 होता हैं | जहां, जैसा कि ऊपर देखा गया है, j = log i। इसका अर्थ है कि खोजे जा रहे अंतराल का आकार 2log i - 2log i - 1 = 2log i - 1 होता है। इससे हमें लॉग का रन टाइम मिलता है (2log i - 1) = log (i) - 1 = O(log i).

और यह एल्गोरिथम को कुल रनटाइम देता है, जिसकी गणना O(log i) + O(log i) = 2 O(log i) = O(log i) के दो चरणों के रनटाइम को जोड़कर की जाती है।

विकल्प

बेंटले और याओ ने घातांकीय खोज के लिए अनेक विविधताएँ प्रस्तुत की हैं । [2] एल्गोरिथम के दूसरे चरण में बाइनरी खोज के लिए ऊपरी सीमा का निर्धारण करते समय, इन विविधताओं में यूनरी खोज के विपरीत, बाइनरी खोज करना सम्मिलित होता है। यह एल्गोरिथम के प्रथम चरण को दो भागों में विभाजित करता है, जिससे एल्गोरिथम कुल मिलाकर तीन-चरण वाला एल्गोरिथम बन जाता है। नया पहला चरण मान निर्धारित करता है, तथा इसमें बहुत कुछ पहले जैसा होता हैं, की खोज कुंजी से अधिक होती है और खोज कुंजी से कम है. प्रथम ,को 2 की अगली घात की गणना करके (अर्थात, 1 को j में जोड़कर) एकात्मक विधि से निर्धारित किया गया था। प्रकारांतर में यह प्रस्तावित है कि इसके अतिरिक्त दोगुना कर दिया गया है (उदाहरण के लिए, 22 के विपरीत 24 से 23 पर कूदना) हैं | पहला ऐसा है कि खोज कुंजी से अधिक होने पर यह प्रथम की तुलना में अधिक कठोर ऊपरी सीमा बनाती है। जब यह पाया जाता है, एल्गोरिथ्म अपने दूसरे चरण में चला जाता है | इसमें और द्वारा गठित अंतराल पर बाइनरी खोज की जाती है, अधिक स्पष्ट ऊपरी सीमा घातांक दे रहा है। यहां से, एल्गोरिदम का तीसरा चरण अंतराल 2j - 1 और 2j पर बाइनरी खोज करता है, प्रथम जैसा = O(log i) इस विविधता का प्रदर्शन होता है।

अतः बेंटले और याओ इस भिन्नता को सामान्यीकृत करते हैं जहां एल्गोरिथ्म के प्रथम चरण के समय बाइनरी खोजों की कोई भी संख्या, k, निष्पादित की जाती है, जिससे k-नेस्टेड बाइनरी खोज भिन्नता मिलती है। मूल घातांकीय खोज एल्गोरिदम की तरह, O(log i) समय में चलने वाली विविधताओं के लिए एसिम्प्टोटिक रनटाइम नहीं परिवर्तित करता है।

इसके अतिरिक्त , जब k-नेस्टेड बाइनरी खोज के उपरोक्त परिणाम का उपयोग क्रमबद्ध सरणी पर किया जाता है, तब डायनामिक फिंगर प्रॉपर्टी के संक्षेप संस्करण के साथ डेटा संरचना दी जा सकती है।[4] इसका उपयोग करते हुए, खोज के समय की गई तुलनाओं की संख्या log (d) + log log (d) + ... + O(log *d) होती हैं, जहां d एक्सेस किए गए अंतिम अवयव और एक्सेस किए जा रहे वर्तमान अवयव के मध्य रैंक का अंतर है । इस प्रकार से यह वर्तमान अवयव तक पहुँचा जाता है।

अनुप्रयोग

इस प्रकार से खोज बैंड को तीव्रता से बढ़ाने पर आधारित एल्गोरिदम O(ns) के लिए अनुक्रम संरेखण का समाधान करता है, जहां n अनुक्रमों की लंबाई है और s उनके मध्य की संपादन दूरी होती है। [5][6]

यह भी देखें

संदर्भ

  1. Baeza-Yates, Ricardo; Salinger, Alejandro (2010), "Fast intersection algorithms for sorted sequences", in Elomaa, Tapio; Mannila, Heikki; Orponen, Pekka (eds.), Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 6060, Springer, pp. 45–61, Bibcode:2010LNCS.6060...45B, doi:10.1007/978-3-642-12476-1_3, ISBN 9783642124754.
  2. 2.0 2.1 Bentley, Jon L.; Yao, Andrew C. (1976). "An almost optimal algorithm for unbounded searching". Information Processing Letters. 5 (3): 82–87. doi:10.1016/0020-0190(76)90071-5. ISSN 0020-0190.
  3. 3.0 3.1 Jonsson, Håkan (2011-04-19). "Exponential Binary Search". Retrieved 2014-03-24.
  4. Andersson, Arne; Thorup, Mikkel (2007). "Dynamic ordered sets with exponential search trees". Journal of the ACM. 54 (3): 13. arXiv:cs/0210006. doi:10.1145/1236457.1236460. ISSN 0004-5411.
  5. Ukkonen, Esko (March 1985). "स्ट्रिंग्स में अनुमानित पैटर्न ढूँढना". Journal of Algorithms. 6 (1): 132–137. doi:10.1016/0196-6774(85)90023-9. ISSN 0196-6774.
  6. Šošić, Martin; Šikić, Mile (2016-08-23). "Edlib: a C/C++ library for fast, exact sequence alignment using edit distance". dx.doi.org. Retrieved 2023-03-17.