घातीय खोज: Difference between revisions
No edit summary |
No edit summary |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 11: | Line 11: | ||
}} | }} | ||
[[कंप्यूटर विज्ञान]] में, | [[कंप्यूटर विज्ञान]] में, '''घातांकीय खोज''' (जिसे दोहरीकरण खोज या तीव्र खोज या स्ट्रुज़िक खोज भी कहा जाता है) <ref name=Baeza-Yates/> यह [[कलन विधि|एल्गोरिथम]] है, जो [[जॉन बेंटले (कंप्यूटर वैज्ञानिक)]] और [[एंड्रयू ची-चिह याओ]] द्वारा 1976 में क्रमबद्ध किया था, इस प्रकार से यह असीमित/अनंत सूचियों की खोज के लिए बनाया गया था। <ref name=PaperBentley/> इसे प्रयुक्त करने के अनेक विधि होती हैं, जिनमें से यह सबसे समान होते है | यह उस सीमा को निर्धारित करना हैं जिसमें खोज कुंजी स्थित होती है और उस सीमा के अन्दर बाइनरी खोज करना होता है। यह ''O''(log ''i'') प्राप्त करता है जहां ''i'' सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है । | ||
इस प्रकार से घातांकीय खोज का उपयोग बंधी हुई सूचियों में खोजने के लिए भी किया जा सकता है। घातांकीय खोज बाउंडेड सूचियों के लिए अधिक पारंपरिक खोजों से भी श्रेष्ठ | इस प्रकार से घातांकीय खोज का उपयोग बंधी हुई सूचियों में खोजने के लिए भी किया जा सकता है। घातांकीय खोज बाउंडेड सूचियों के लिए अधिक पारंपरिक खोजों से भी श्रेष्ठ प्रदर्शन कर सकती है, जैसे कि बाइनरी खोज, जब खोजी जा रही अवयव सरणी के प्रारंभ में समीप होता है। किन्तु ऐसा इसलिए है क्योंकि घातांकीय खोज O(log i) समय में चलेगी, जहां i सूची में खोजे जा रहे अवयव का सूचकांक होता है, जबकि बाइनरी खोज O(log n) समय में चलेगी, जहां n अवयवों की सूची में संख्या है । | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
घातांकीय खोज | किन्तु घातांकीय खोज निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण प्रमुख होते हैं. प्रथम चरण सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होती है । दूसरे चरण में, इस श्रेणी पर बाइनरी खोज की जाती है। प्रथम चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम प्रथम [[घातांक]], ''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}} यदि खोज कुंजी सूची में नहीं होते है,इस सूची में खोज कुंजी की स्थित है, तब बाइनरी खोज यह तब किसी विफलता के परिणाम के साथ की जाती है। | ||
== प्रदर्शन == | == प्रदर्शन == | ||
एल्गोरिदम के प्रथम | एल्गोरिदम के प्रथम चरण में ''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(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 की अगली घात की गणना करके (अर्थात, 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-नेस्टेड बाइनरी खोज भिन्नता मिलती है। मूल घातांकीय खोज एल्गोरिदम की तरह, ''O''(log ''i'') समय में चलने वाली विविधताओं के लिए एसिम्प्टोटिक रनटाइम नहीं परिवर्तित करता है। | ||
इसके अतिरिक्त , जब k-नेस्टेड बाइनरी खोज के उपरोक्त परिणाम का उपयोग क्रमबद्ध सरणी पर किया जाता है, | इसके अतिरिक्त , जब 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> | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[रेखीय खोज]] | *[[रेखीय खोज]] | ||
| Line 107: | Line 107: | ||
</ref> | </ref> | ||
}} | }} | ||
[[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
| Class | Search algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(log i) |
| Best-case performance | O(1) |
| Average performance | O(log i) |
| Worst-case space complexity | O(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]
यह भी देखें
- रेखीय खोज
- द्विआधारी खोज
- अंतर्वेशन खोज
- टर्नरी खोज
- हैश तालिका
संदर्भ
- ↑ 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.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.0 3.1 Jonsson, Håkan (2011-04-19). "Exponential Binary Search". Retrieved 2014-03-24.
- ↑ 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.
- ↑ Ukkonen, Esko (March 1985). "स्ट्रिंग्स में अनुमानित पैटर्न ढूँढना". Journal of Algorithms. 6 (1): 132–137. doi:10.1016/0196-6774(85)90023-9. ISSN 0196-6774.
- ↑ Š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.
