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

From Vigyanwiki
No edit summary
No edit summary
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>
==यह भी देखें==
==यह भी देखें==
*[[रेखीय खोज]]
*[[रेखीय खोज]]

Revision as of 17:48, 5 July 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=घातीय_खोज&oldid=235329’