रेखीय खोज: Difference between revisions

रेखीय खोज
Class	Search algorithm
Worst-case performance	O(n)
Best-case performance	O(1)
Average performance	O(n)
Worst-case space complexity	O(1) iterative

Revision as of 15:29, 5 July 2023

कंप्यूटर विज्ञान में, रैखिक खोज या अनुक्रमिक खोज सूची (कंप्यूटिंग) के अंदर तत्व खोजने की विधि होती है। यह सूची के प्रत्येक तत्व की क्रमिक रूप से जांच करता है जब तक कि कोई मिलान नहीं मिल जाता या पूर्ण सूची खोज नहीं ली जाती है ।^[1]

इस प्रकार से एक रेखीय खोज सबसे व्यर्थ समय जटिलता या रैखिक समय में चलती रहती है और अधिकतम $n$ तुलना करती है जहाँ $n$ सूची की लंबाई है ।यदि प्रत्येक तत्व को खोजे जाने की समान संभावना है, तो रैखिक $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n+1/2$ खोज की औसत स्तिथि होती है तुलना, किन्तु यदि प्रत्येक तत्व के लिए खोज संभावनाएं भिन्न होती हैं तो औसत स्तिथि प्रभावित हो सकती है। और रैखिक खोज संभवतः ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि बाइनरी खोज एल्गोरिदम और हैश तालिका , छोटी सूचियों को छोड़कर सभी के लिए अधिक तीव्र खोज की अनुमति देती हैं।^[2]

एल्गोरिदम

अतः रैखिक खोज क्रमिक रूप से सूची के प्रत्येक तत्व की जांच करती है जब तक कि उसे लक्ष्य मान से मेल खाने वाला तत्व नहीं मिल जाता है । और यदि कलन विधि सूची के अंत तक पहुँच जाता है, तो खोज असफल रूप से समाप्त हो जाती है।^[1]

मूल एल्गोरिदम

मूल्यों या रिकॉर्ड $L 0 .... L n -1$ , और लक्ष्य मान $T$ के साथ $n$ तत्वों की एक सूची $L$ को देखते हुए, निम्नलिखित सबरूटीन $L$ में लक्ष्य $T$ के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है।^[3]

$i$ को 0 पर सेट करें.
यदि $L i = T$ , खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना $i$ .
$i$ को 1 से बढ़ाएँ.
यदि $i < n$ , चरण 2 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

एक प्रहरी के साथ

इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या Li T के समान है, और दूसरा यह जांचने के लिए कि क्या मैं अभी भी सूची के वैध सूचकांक $i$ को इंगित करता हूं। सूची में एक अतिरिक्त रिकॉर्ड $L n$ (एक प्रहरी मान) जोड़कर जो लक्ष्य के समान है, खोज के अंत तक दूसरी तुलना को समाप्त किया जा सकता है, जिससे एल्गोरिदम तीव्र हो जाता है। यदि लक्ष्य सूची में सम्मिलित नहीं होते है तो खोज प्रहरी तक पहुंच जाती है। ^[4]

$i$ को 0 पर सेट करें.
यदि $L i = T$ , चरण 4 पर जाएँ।
$i$ को 1 से बढ़ाएँ और चरण 2 पर जाएँ।
यदि $i < n$ , खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना $i$ . अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

एक आदेशित तालिका में

अतः यदि सूची इस प्रकार क्रमबद्ध होती है की $L 0 \leq L 1 ... \leq L n -1$ , खोज बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तीव्र से स्थापित कर सकती है जब $L i$ लक्ष्य से अधिक है। इस भिन्नता के लिए ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक उच्च हो।^[5]

$i$ को 0 पर सेट करें.
यदि $L i \geq T$ , चरण 4 पर जाएँ।
$i$ को 1 से बढ़ाएँ और चरण 2 पर जाएँ।
यदि $L i = T$ , खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना $i$ . अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

विश्लेषण

इस प्रकार से n आइटम वाली सूची के लिए, सबसे सही स्तिथि तब होती है जब मान सूची के पहले तत्व के समान होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे व्यर्थ स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।

यदि मांगा जा रहा मूल्य सूची में k बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है

{\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}

उदाहरण के लिए, यदि मांगा जा रहा मूल्य सूची में बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है ${\frac {n+1}{2}}$ है. चूँकि , यदि यह ज्ञात है कि यह बार होता है, तो अधिकतम n - 1 तुलनाओं की आवश्यकता होती है, और तुलनाओं की अपेक्षित संख्या है

\displaystyle {\frac {(n+2)(n-1)}{2n}}

(उदाहरण के लिए, n = 2 के लिए यह 1 है, जो एकल यदि-तब-अन्यथा निर्माण के अनुरूप है)।

किसी भी प्रकार से, असम्बद्ध रूप से सबसे व्यर्थ स्थिति की निवेश और रैखिक खोज की अपेक्षित निवेश दोनों O(n) हैं।

गैर-समान संभावनाएँ

चूँकि यदि वांछित मान सूची के अंत की तुलना में प्रारंभ के निकट होने की अधिक संभावना है, तो रैखिक खोज का प्रदर्शन श्रेष्ठ हो जाता है। इसलिए, यदि कुछ मूल्यों को दूसरों की तुलना में खोजे जाने की अधिक संभावना होती है, तो उन्हें सूची की प्रारंभ में रखना वांछनीय है।

विशेष रूप से, जब सूची आइटम को घटती संभावना के क्रम में व्यवस्थित किया जाता है, और ये संभावनाएं ज्यामितीय रूप से वितरित किया जाता हैं, तो रैखिक खोज की निवेश केवल O(1) होती है। ^[6]

आवेदन

इस प्रकार से रैखिक खोज को प्रयुक्त करना सामान्यतः अधिक सरल होता है, और व्यावहारिक होता है जब सूची में केवल कुछ तत्व होते हैं, या बिना क्रम वाली सूची में एकल खोज करते समय उपयोग किया जाता है ।

तत्पश्चात सूची में कई मानों को खोजना होता है, तो तीव्र विधि का उपयोग करने के लिए सदैव सूची को पूर्व-संसाधित करना पड़ता है। उदाहरण के लिए, कोई सूची को क्रमबद्ध कर सकता है और बाइनरी खोज एल्गोरिदम का उपयोग कर सकता है, या इससे कुशल खोज डेटा संरचना बना सकता है। क्या सूची की सामग्री बार-बार परिवर्तित होती रहती है, बार-बार पुनर्संगठन करने से अधिक असुविधा हो सकती है।

परिणामस्वरूप, भले ही सिद्धांत रूप में अन्य खोज एल्गोरिदम रैखिक खोज (उदाहरण के लिए बाइनरी खोज) से तीव्र हो सकते हैं, व्यवहार में यहां तक कि मध्यम आकार के सरणियों (लगभग 100 आइटम या उससे कम) पर भी किसी और चीज़ का उपयोग करना संभव नहीं हो सकता है। इस प्रकार से उच्च सरणियों पर, यदि डेटा पर्याप्त उच्च होता है तो अन्य, तीव्र खोज विधियों का उपयोग करना ही समझ में आता है, क्योंकि डेटा को तैयार (सॉर्ट) करने का प्रारंभिक समय कई रैखिक खोजों के समान होता है।^[7]

यह भी देखें

टर्नरी खोज
हैश तालिका
रेखीय खोज समस्या

संदर्भ

उद्धरण

↑ ^1.0 ^1.1 Knuth 1998, §6.1 ("Sequential search").
↑ Knuth 1998, §6.2 ("Searching by Comparison Of Keys").
↑ Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm B".
↑ Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm Q".
↑ Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm T".
↑ Knuth, Donald (1997). "Section 6.1: Sequential Searching". Sorting and Searching. The Art of Computer Programming. Vol. 3 (3rd ed.). Addison-Wesley. pp. 396–408. ISBN 0-201-89685-0.
↑ Horvath, Adam. ".NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन". Retrieved 19 April 2013.

कार्य

Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 0-201-89685-0

श्रेणी:खोज एल्गोरिदम

[FOOTNOTEKnuth1998§6.1_("Sequential_search")-1] 1.0 ^1.1 Knuth 1998, §6.1 ("Sequential search").

[FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_Of_Keys")-2] Knuth 1998, §6.2 ("Searching by Comparison Of Keys").

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_B"-3] Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm B".

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_Q"-4] Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm Q".

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_T"-5] Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm T".

[knuth-6] Knuth, Donald (1997). "Section 6.1: Sequential Searching". Sorting and Searching. The Art of Computer Programming. Vol. 3 (3rd ed.). Addison-Wesley. pp. 396–408. ISBN 0-201-89685-0.

[7] Horvath, Adam. ".NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन". Retrieved 19 April 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 9: / Line 9: @@
 }}
-[[कंप्यूटर विज्ञान]] में, रैखिक खोज या अनुक्रमिक खोज [[सूची (कंप्यूटिंग)]] के अंदर   तत्व खोजने की विधि होती  है। यह सूची के प्रत्येक तत्व की क्रमिक रूप से जांच करता है जब तक कि कोई मिलान नहीं मिल जाता या पूर्ण  सूची खोज नहीं ली जाती है ।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}
+[[कंप्यूटर विज्ञान]] में, '''रैखिक खोज''' या '''अनुक्रमिक खोज''' [[सूची (कंप्यूटिंग)]] के अंदर   तत्व खोजने की विधि होती  है। यह सूची के प्रत्येक तत्व की क्रमिक रूप से जांच करता है जब तक कि कोई मिलान नहीं मिल जाता या पूर्ण  सूची खोज नहीं ली जाती है ।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}
 इस प्रकार से एक रेखीय खोज सबसे व्यर्थ  समय जटिलता या रैखिक समय में चलती रहती  है और अधिकतम {{math|''n''}} तुलना करती  है  जहाँ  {{math|''n''}} सूची की लंबाई है ।यदि प्रत्येक तत्व को खोजे जाने की समान संभावना है, तो रैखिक {{math|{{Sfrac|''n+1''|2}}}} खोज की  औसत  स्तिथि  होती  है  तुलना, किन्तु  यदि प्रत्येक तत्व के लिए खोज संभावनाएं भिन्न होती हैं तो औसत  स्तिथि  प्रभावित हो सकती  है। और रैखिक खोज संभवतः  ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि [[बाइनरी खोज एल्गोरिदम]] और [[ हैश तालिका |हैश तालिका]] , छोटी सूचियों को छोड़कर सभी के लिए अधिक तीव्र  खोज की अनुमति देती हैं।{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison Of Keys")}}
@@ Line 17: / Line 17: @@
 ===मूल एल्गोरिदम===
-एक सूची दी गई {{math|''L''}} का {{math|''n''}} मान या रिकॉर्ड वाले तत्व (कंप्यूटर विज्ञान) {{math|''L''<sub>0</sub> .... ''L''<sub>''n''−1</sub>}}, और लक्ष्य मान {{math|''T''}}, निम्नलिखित  लक्ष्य के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है {{math|''T''}} में {{math|''L''}}.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm B"}}
+मूल्यों या रिकॉर्ड {{math|''L''<sub>0</sub> .... ''L''<sub>''n''−1</sub>}}, और लक्ष्य मान {{math|''T''}} के साथ {{math|''n''}} तत्वों की एक सूची {{math|''L''}} को देखते हुए, निम्नलिखित [[सबरूटीन]] {{math|''L''}} में लक्ष्य {{math|''T''}} के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm B"}}
-मूल्यों या रिकॉर्ड {{math|''L''<sub>0</sub> .... ''L''<sub>''n''−1</sub>}}, और लक्ष्य मान {{math|''T''}} के साथ {{math|''n''}} तत्वों की एक सूची {{math|''L''}} को देखते हुए, निम्नलिखित [[सबरूटीन]] {{math|''L''}} में लक्ष्य {{math|''T''}} के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है।
+# {{math|''i''}} को 0 पर सेट करें.
+# यदि  {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}.
+# {{math|''i''}} को 1 से बढ़ाएँ.
+# यदि  {{math|''i'' < ''n''}}, चरण 2 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
-# तय करना {{math|''i''}} से 0.
+===एक प्रहरी के साथ  ===
-# अगर {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}.
+इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या ''{{math|''L''<sub>''i''</sub>}}'' ''T'' के समान  है, और दूसरा यह जांचने के लिए कि क्या मैं अभी भी सूची के वैध सूचकांक {{math|''i''}} को इंगित करता हूं। सूची में एक अतिरिक्त रिकॉर्ड {{math|''L''<sub>''n''</sub>}}  (एक प्रहरी मान) जोड़कर जो लक्ष्य के समान  है,  खोज के अंत तक दूसरी तुलना को समाप्त किया जा सकता है, जिससे एल्गोरिदम तीव्र हो जाता है। यदि लक्ष्य सूची में सम्मिलित  नहीं होते  है तो खोज प्रहरी तक पहुंच जाती है। {{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm Q"}}
-# बढ़ोतरी {{math|''i''}} 1 से.
-# अगर {{math|''i'' < ''n''}}, चरण 2 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
-===एक प्रहरी के साथ===
+# {{math|''i''}} को 0 पर सेट करें.
-उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: यह जांचने के लिए कि क्या {{math|''L''<sub>''i''</sub>}} टी के बराबर है, और दूसरा यह जांचने के लिए है {{math|''i''}} अभी भी सूची के वैध सूचकांक की ओर इशारा करता है। अतिरिक्त रिकॉर्ड जोड़कर {{math|''L''<sub>''n''</sub>}} सूची में (एक प्रहरी मान) जो लक्ष्य के बराबर है, दूसरी तुलना को खोज के अंत तक समाप्त किया जा सकता है, जिससे एल्गोरिदम तेज़ हो जाता है। यदि लक्ष्य सूची में शामिल नहीं है तो खोज प्रहरी तक पहुंच जाएगी।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm Q"}}
+# यदि  {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, चरण 4 पर जाएँ।
+# {{math|''i''}} को 1 से बढ़ाएँ और चरण 2 पर जाएँ।
-# तय करना {{math|''i''}} से 0.
+# यदि  {{math|''i'' < ''n''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}. अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
-# अगर {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, चरण 4 पर जाएँ।
-# बढ़ोतरी {{math|''i''}} 1 से और चरण 2 पर जाएँ।
-# अगर {{math|''i'' < ''n''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}. अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
 ===एक आदेशित तालिका में===
-यदि सूची इस प्रकार क्रमबद्ध है {{math|''L''<sub>0</sub> &le; ''L''<sub>1</sub> ... &le; ''L''<sub>''n''−1</sub>}}, खोज बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तेज़ी से स्थापित कर सकती है {{math|''L''<sub>''i''</sub>}} लक्ष्य से अधिक है। इस भिन्नता के लिए ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक बड़ा हो।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm T"}}
+अतः यदि सूची इस प्रकार क्रमबद्ध होती है की  {{math|''L''<sub>0</sub> &le; ''L''<sub>1</sub> ... &le; ''L''<sub>''n''−1</sub>}}, खोज बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तीव्र से स्थापित कर सकती है जब  {{math|''L''<sub>''i''</sub>}} लक्ष्य से अधिक है। इस भिन्नता के लिए ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक उच्च हो।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm T"}}
-# तय करना {{math|''i''}} से 0.
+# {{math|''i''}} को 0 पर सेट करें.
-# अगर {{math|''L''<sub>''i''</sub> &ge; ''T''}}, चरण 4 पर जाएँ।
+# यदि  {{math|''L''<sub>''i''</sub> &ge; ''T''}}, चरण 4 पर जाएँ।
-# बढ़ोतरी {{math|''i''}} 1 से और चरण 2 पर जाएँ।
+# {{math|''i''}} को 1 से बढ़ाएँ और चरण 2 पर जाएँ।
-# अगर {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}. अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
+# यदि  {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}. अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
 ==विश्लेषण==
-एन आइटम वाली सूची के लिए, सबसे अच्छा  स्तिथि  तब होता है जब मान सूची के पहले तत्व के बराबर होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे व्यर्थ  स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
+इस प्रकार से n आइटम वाली सूची के लिए, सबसे सही   स्तिथि  तब होती  है जब मान सूची के पहले तत्व के समान  होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे व्यर्थ  स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
 यदि मांगा जा रहा मूल्य सूची में k बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है
@@ Line 53: / Line 51: @@
 \end{cases}
 </math>
-उदाहरण के लिए, यदि मांगा जा रहा मूल्य सूची में बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है <math>\frac{n + 1}2</math>. हालाँकि, यदि यह ज्ञात है कि यह बार होता है, तो अधिकतम n - 1 तुलनाओं की आवश्यकता होती है, और तुलनाओं की अपेक्षित संख्या है
+उदाहरण के लिए, यदि मांगा जा रहा मूल्य सूची में बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है <math>\frac{n + 1}2</math> है. चूँकि , यदि यह ज्ञात है कि यह बार होता है, तो अधिकतम n - 1 तुलनाओं की आवश्यकता होती है, और तुलनाओं की अपेक्षित संख्या है
 :<math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>
-(उदाहरण के लिए, n = 2 के लिए यह 1 है, जो एकल if-then-else निर्माण के अनुरूप है)।
+(उदाहरण के लिए, n = 2 के लिए यह 1 है, जो एकल यदि-तब-अन्यथा निर्माण के अनुरूप है)।
-किसी भी तरह से, [[स्पर्शोन्मुख जटिलता]] सबसे व्यर्थ  स्थिति की लागत और रैखिक खोज की अपेक्षित लागत दोनों बड़े ओ अंकन (एन) हैं।
+किसी भी प्रकार  से,  [[स्पर्शोन्मुख जटिलता|असम्बद्ध रूप से]] सबसे व्यर्थ  स्थिति की निवेश  और रैखिक खोज की अपेक्षित निवेश  दोनों O(''n'') हैं।
 ===गैर-समान संभावनाएँ===
-यदि वांछित मान सूची के अंत की तुलना में शुरुआत के करीब होने की अधिक संभावना है, तो रैखिक खोज का प्रदर्शन बेहतर हो जाता है। इसलिए, यदि कुछ मूल्यों को दूसरों की तुलना में खोजे जाने की अधिक संभावना है, तो उन्हें सूची की शुरुआत में रखना वांछनीय है।
+चूँकि यदि वांछित मान सूची के अंत की तुलना में प्रारंभ  के निकट  होने की अधिक संभावना है, तो रैखिक खोज का प्रदर्शन श्रेष्ठ हो जाता है। इसलिए, यदि कुछ मूल्यों को दूसरों की तुलना में खोजे जाने की अधिक संभावना होती है, तो उन्हें सूची की प्रारंभ  में रखना वांछनीय है।
-विशेष रूप से, जब सूची आइटम को घटती संभावना के क्रम में व्यवस्थित किया जाता है, और ये संभावनाएं [[ज्यामितीय वितरण]] होती हैं, तो रैखिक खोज की लागत केवल O(1) होती है। <ref name="knuth">
+विशेष रूप से, जब सूची आइटम को घटती संभावना के क्रम में व्यवस्थित किया जाता है, और ये संभावनाएं [[ज्यामितीय वितरण|ज्यामितीय]]  रूप से वितरित किया जाता  हैं, तो रैखिक खोज की निवेश  केवल O(1) होती है। <ref name="knuth">
    {{cite book
    | first=Donald |last=Knuth |author-link=Donald Knuth
@@ Line 76: / Line 74: @@
 </ref>
 ==आवेदन==
-रैखिक खोज को लागू करना आम तौर पर बहुत सरल होता है, और व्यावहारिक होता है जब सूची में केवल कुछ तत्व होते हैं, या बिना क्रम वाली सूची में एकल खोज करते समय।
+इस प्रकार से रैखिक खोज को प्रयुक्त   करना सामान्यतः   अधिक   सरल होता है, और व्यावहारिक होता है जब सूची में केवल कुछ तत्व होते हैं, या बिना क्रम वाली सूची में एकल खोज करते समय उपयोग किया जाता है ।
-जब ही सूची में कई मानों को खोजना होता है, तो तेज़ विधि का उपयोग करने के लिए अक्सर सूची को पूर्व-संसाधित करना पड़ता है। उदाहरण के लिए, कोई सूची को [[ सॉर्ट करें (कंप्यूटिंग) |सॉर्ट करें (कंप्यूटिंग)]] कर सकता है और बाइनरी खोज एल्गोरिदम का उपयोग कर सकता है, या इससे कुशल खोज डेटा संरचना बना सकता है। क्या सूची की सामग्री बार-बार बदलती रहती है, बार-बार पुनर्संगठन करने से अधिक परेशानी हो सकती है।
+तत्पश्चात  सूची में कई मानों को खोजना होता है, तो तीव्र  विधि का उपयोग करने के लिए सदैव   सूची को पूर्व-संसाधित करना पड़ता है। उदाहरण के लिए, कोई सूची को  [[ सॉर्ट करें (कंप्यूटिंग) |क्रमबद्ध]] कर सकता है और बाइनरी खोज एल्गोरिदम का उपयोग कर सकता है, या इससे कुशल खोज डेटा संरचना बना सकता है। क्या सूची की सामग्री बार-बार परिवर्तित होती   रहती है, बार-बार पुनर्संगठन करने से अधिक असुविधा हो सकती है।
-परिणामस्वरूप, भले ही सिद्धांत रूप में अन्य खोज एल्गोरिदम रैखिक खोज (उदाहरण के लिए बाइनरी खोज) से तेज़ हो सकते हैं, व्यवहार में यहां तक कि मध्यम आकार के सरणियों (लगभग 100 आइटम या उससे कम) पर भी किसी और चीज़ का उपयोग करना संभव नहीं हो सकता है। बड़े सरणियों पर, यदि डेटा पर्याप्त बड़ा है तो अन्य, तेज़ खोज विधियों का उपयोग करना ही समझ में आता है, क्योंकि डेटा को तैयार (सॉर्ट) करने का प्रारंभिक समय कई रैखिक खोजों के बराबर होता है।<ref>{{Cite web |first=Adam |last=Horvath |url=http://blog.teamleadnet.com/2012/02/quicksort-binary-search-and-linear.html |title=.NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन|access-date=19 April 2013 }}</ref>
+परिणामस्वरूप, भले ही सिद्धांत रूप में अन्य खोज एल्गोरिदम रैखिक खोज (उदाहरण के लिए बाइनरी खोज) से तीव्र  हो सकते हैं, व्यवहार में यहां तक कि मध्यम आकार के सरणियों (लगभग 100 आइटम या उससे कम) पर भी किसी और चीज़ का उपयोग करना संभव नहीं हो सकता है। इस प्रकार से उच्च   सरणियों पर, यदि डेटा पर्याप्त उच्च होता   है तो अन्य, तीव्र खोज विधियों का उपयोग करना ही समझ में आता है, क्योंकि डेटा को तैयार (सॉर्ट) करने का प्रारंभिक समय कई रैखिक खोजों के समान  होता है।<ref>{{Cite web |first=Adam |last=Horvath |url=http://blog.teamleadnet.com/2012/02/quicksort-binary-search-and-linear.html |title=.NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन|access-date=19 April 2013 }}</ref>
 ==यह भी देखें==
 * [[टर्नरी खोज]]

Anonymous

Search

रेखीय खोज: Difference between revisions

Namespaces

More

Page actions

Revision as of 15:29, 5 July 2023

Contents

एल्गोरिदम

मूल एल्गोरिदम

एक प्रहरी के साथ

एक आदेशित तालिका में

विश्लेषण

गैर-समान संभावनाएँ

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रेखीय खोज: Difference between revisions

Revision as of 15:29, 5 July 2023

एल्गोरिदम

मूल एल्गोरिदम

एक प्रहरी के साथ

एक आदेशित तालिका में

विश्लेषण

गैर-समान संभावनाएँ

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Wiki tools

Page tools

Other projects

Hidden categories