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

From Vigyanwiki
(Created page with "{{Short description|Algorithm for searching sorted, infinite lists}} {{Infobox algorithm |class=Search algorithm |image= |data=Array |time=big O...")
 
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/>इसे लागू करने के कई तरीके हैं, जिनमें से सबसे आम है उस सीमा को निर्धारित करना जिसमें खोज कुंजी स्थित है और उस सीमा के भीतर   बाइनरी खोज करना है। यह बिग-ओ नोटेशन (लॉग i) लेता है जहां i सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है सूची।


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


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


<syntaxhighlight lang="cpp">
<syntaxhighlight lang="cpp">
Line 40: Line 40:
== प्रदर्शन ==
== प्रदर्शन ==


एल्गोरिदम के पहले चरण में 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(लॉग 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) समय लेता है। चूंकि दूसरा चरण केवल एक द्विआधारी खोज है, इसमें 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(लॉग एन) लिया जाता है जहां 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 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 की अगली घात की गणना करके (अर्थात, 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).


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


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


== संदर्भ ==
== संदर्भ ==
<!--- See [[Wikipedia:Footnotes]] on how to create references using<ref></ref> tags which will then appear here automatically -->
 
{{Reflist|refs=
{{Reflist|refs=
<ref name=Baeza-Yates>{{citation|contribution=Fast intersection algorithms for sorted sequences|first1=Ricardo|last1=Baeza-Yates|author1-link= Ricardo Baeza-Yates |first2=Alejandro|last2=Salinger|title=Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday|volume=6060|series=Lecture Notes in Computer Science|editor1-first=Tapio|editor1-last=Elomaa|editor2-first=Heikki|editor2-last=Mannila|editor2-link=Heikki Mannila|editor3-first=Pekka|editor3-last=Orponen|publisher=Springer|year=2010|isbn=9783642124754|pages=45–61|doi=10.1007/978-3-642-12476-1_3|bibcode=2010LNCS.6060...45B}}.</ref>
<ref name=Baeza-Yates>{{citation|contribution=Fast intersection algorithms for sorted sequences|first1=Ricardo|last1=Baeza-Yates|author1-link= Ricardo Baeza-Yates |first2=Alejandro|last2=Salinger|title=Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday|volume=6060|series=Lecture Notes in Computer Science|editor1-first=Tapio|editor1-last=Elomaa|editor2-first=Heikki|editor2-last=Mannila|editor2-link=Heikki Mannila|editor3-first=Pekka|editor3-last=Orponen|publisher=Springer|year=2010|isbn=9783642124754|pages=45–61|doi=10.1007/978-3-642-12476-1_3|bibcode=2010LNCS.6060...45B}}.</ref>

Revision as of 16:08, 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]इसे लागू करने के कई तरीके हैं, जिनमें से सबसे आम है उस सीमा को निर्धारित करना जिसमें खोज कुंजी स्थित है और उस सीमा के भीतर बाइनरी खोज करना है। यह बिग-ओ नोटेशन (लॉग i) लेता है जहां i सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है सूची।

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

एल्गोरिथम

घातीय खोज निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण होते हैं. पहला चरण सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होगी। दूसरे चरण में, इस श्रेणी पर बाइनरी खोज की जाती है। पहले चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम पहले घातांक, जे की तलाश करता है, जहां मान 2 हैj खोज कुंजी से बड़ा है. यह मान, 2j 2, 2 की पिछली शक्ति के साथ बाइनरी खोज के लिए ऊपरी सीमा बन जाता हैj - 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(लॉग i) समय लगता है, जहां i वह सूचकांक है जहां सूची में खोज कुंजी होगी। ऐसा इसलिए है, क्योंकि बाइनरी खोज के लिए ऊपरी सीमा निर्धारित करने में, जबकि लूप बिल्कुल निष्पादित होता है बार. चूंकि सूची को खोज सूचकांक को दोगुना करने के बाद क्रमबद्ध किया गया है कई बार, एल्गोरिथ्म खोज सूचकांक पर होगा जो कि i से अधिक या उसके बराबर है . इस प्रकार, एल्गोरिथम के पहले चरण में O(log i) समय लगता है।

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

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

विकल्प

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

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

इसके अलावा, जब के-नेस्टेड बाइनरी खोज के उपरोक्त परिणाम का उपयोग क्रमबद्ध सरणी पर किया जाता है, तो बिखरा हुआ पेड़ के तंग संस्करण के साथ डेटा संरचना दी जा सकती है।[4]इसका उपयोग करते हुए, खोज के दौरान की गई तुलनाओं की संख्या लॉग (डी) + लॉग लॉग (डी) + ... + ओ (लॉग) है*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=235328’