रेखीय खोज: 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:31, 30 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 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

प्रहरी के साथ

इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है | यह जांचने के लिए कि क्या L_i 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")}}
+इस प्रकार से रेखीय खोज सबसे व्यर्थ समय सम्मिश्रता या रैखिक समय में चलती रहती है और अधिकतम {{math|''n''}} तुलना करती है जहाँ {{math|''n''}} सूची की लंबाई है । यदि प्रत्येक अवयव को खोजे जाने की समान संभावना है, तब रैखिक {{math|{{Sfrac|''n+1''|2}}}} खोज की औसत स्तिथि होती है तुलना, किन्तु यदि प्रत्येक अवयव के लिए खोज संभावनाएं भिन्न होती हैं तब औसत स्तिथि प्रभावित हो सकती है। और रैखिक खोज संभवतः ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं हैं, जैसे कि [[बाइनरी खोज एल्गोरिदम]] और [[ हैश तालिका |हैश तालिका]] , लघु सूचियों को छोड़कर सभी के लिए अधिक तीव्र खोज की अनुमति देती हैं। {{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison Of Keys")}}
 ==एल्गोरिदम==
-अतः रैखिक खोज क्रमिक रूप से सूची के प्रत्येक तत्व की जांच करती है जब तक कि उसे लक्ष्य मान से मेल खाने वाला तत्व नहीं मिल जाता है । और यदि [[कलन विधि]] सूची के अंत तक पहुँच जाता है, तो खोज असफल रूप से समाप्त हो जाती है।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}
+अतः रैखिक खोज क्रमिक रूप से सूची के प्रत्येक अवयव की जांच करती है जब तक कि उसे लक्ष्य मान से मेल खाने वाला अवयव नहीं मिल जाता है । और यदि [[कलन विधि|एल्गोरिदम विधि]] सूची के अंत तक पहुँच जाता है, तब खोज असफल रूप से समाप्त हो जाती है। {{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}
 ===मूल एल्गोरिदम===
-मूल्यों या रिकॉर्ड {{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''}} के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm B"}}
-# {{math|''i''}} को 0 पर सेट करें.
+# {{math|''i''}} को 0 पर समुच्चय करते हैं |
-# यदि {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}.
+# यदि {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है | वापस करना {{math|''i''}} हैं |
-# {{math|''i''}} को 1 से बढ़ाएँ.
+# {{math|''i''}} को 1 से बढ़ाएँ जाते हैं |
 # यदि {{math|''i'' < ''n''}}, चरण 2 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
-===एक प्रहरी के साथ  ===
+===प्रहरी के साथ  ===
-इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या ''{{math|''L''<sub>''i''</sub>}}'' ''T'' के समान है, और दूसरा यह जांचने के लिए कि क्या मैं अभी भी सूची के वैध सूचकांक {{math|''i''}} को इंगित करता हूं। सूची में एक अतिरिक्त रिकॉर्ड {{math|''L''<sub>''n''</sub>}} (एक प्रहरी मान) जोड़कर जो लक्ष्य के समान है, खोज के अंत तक दूसरी तुलना को समाप्त किया जा सकता है, जिससे एल्गोरिदम तीव्र हो जाता है। यदि लक्ष्य सूची में सम्मिलित नहीं होते है तो खोज प्रहरी तक पहुंच जाती है। {{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm Q"}}
+इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है | यह जांचने के लिए कि क्या ''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''}} को 0 पर सेट करें.
+# {{math|''i''}} को 0 पर समुच्चय करें.
 # यदि {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, चरण 4 पर जाएँ।
 # {{math|''i''}} को 1 से बढ़ाएँ और चरण 2 पर जाएँ।
-# यदि {{math|''i'' < ''n''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}. अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
+# यदि {{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|''i''}} को 1 से बढ़ाएँ और चरण 2 पर जाएँ।
-# यदि {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना {{math|''i''}}. अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
+# यदि {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, खोज सफलतापूर्वक समाप्त हो जाती है | तब विपरीत {{math|''i''}}. होती हैं | अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
 ==विश्लेषण==
-इस प्रकार से n आइटम वाली सूची के लिए, सबसे सही   स्तिथि तब होती है जब मान सूची के पहले तत्व के समान होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे व्यर्थ स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
+इस प्रकार से ''n'' आइटम वाली सूची के लिए, सबसे उत्तम स्तिथि तब होती है जब मान सूची के पहले अवयव के समान होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे व्यर्थ स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल होता है), उस स्थिति में ''n'' तुलना की आवश्यकता होती है।
-यदि मांगा जा रहा मूल्य सूची में k बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है
+यदि मांगा जा रही मूल्य सूची में ''k'' आता है, और सूची के सभी क्रम समान रूप से संभावित होते हैं, तब तुलनाओं की अपेक्षित संख्या है |
 :<math>
@@ Line 51: / 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 है, जो एकल यदि-तब-अन्यथा निर्माण के अनुरूप है)।
+(उदाहरण के लिए, ''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 74: / 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:31, 30 July 2023

Contents

एल्गोरिदम

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

प्रहरी के साथ

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 15:31, 30 July 2023

एल्गोरिदम

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

प्रहरी के साथ

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Wiki tools

Page tools

Other projects

Hidden categories