रेखीय खोज: 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

Latest revision as of 13:15, 3 August 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 1: / Line 1: @@
-{{short description|Sequentially looking in an array}}
+{{short description|Sequentially looking in an array}}{{Infobox algorithm
-{{Multiple issues|
-{{refimprove|date=November 2010}}
-{{one source|date=November 2010}}
-}}
-{{Infobox algorithm
 |name={{PAGENAMEBASE}}|class=[[Search algorithm]]
 |time=[[big O notation#Orders of common functions|''O''(''n'')]]
@@ Line 15: / 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''}} का {{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|''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|''i'' < ''n''}}, चरण 2 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।
-===एक प्रहरी के साथ===
+===प्रहरी के साथ  ===
-उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या {{math|''L''<sub>''i''</sub>}} टी के बराबर है, और दूसरा यह जांचने के लिए है {{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|''L''<sub>''i''</sub> {{=}} ''T''}}, चरण 4 पर जाएँ।
-# बढ़ोतरी {{math|''i''}} 1 से और चरण 2 पर जाएँ।
+# {{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|''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 बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है
+यदि मांगा जा रही मूल्य सूची में ''k'' आता है, और सूची के सभी क्रम समान रूप से संभावित होते हैं, तब तुलनाओं की अपेक्षित संख्या है |
 :<math>
@@ Line 57: / 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 79: / Line 73: @@
    }}
 </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>
 ==यह भी देखें==
 * [[टर्नरी खोज]]
@@ Line 95: / Line 85: @@
 ==संदर्भ==
 ===उद्धरण===
 {{Reflist}}
 ===कार्य===
@@ Line 108: / Line 94: @@
 श्रेणी:खोज एल्गोरिदम
+[[Category:Created On 25/06/2023|Linear Search]]
-[[Category: Machine Translated Page]]
+[[Category:Lua-based templates|Linear Search]]
-[[Category:Created On 25/06/2023]]
+[[Category:Machine Translated Page|Linear Search]]
+[[Category:Pages with script errors|Linear Search]]
+[[Category:Short description with empty Wikidata description|Linear Search]]
+[[Category:Templates Vigyan Ready|Linear Search]]
+[[Category:Templates that add a tracking category|Linear Search]]
+[[Category:Templates that generate short descriptions|Linear Search]]
+[[Category:Templates using TemplateData|Linear Search]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 13:15, 3 August 2023

Contents

एल्गोरिदम

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

प्रहरी के साथ

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 13:15, 3 August 2023

एल्गोरिदम

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

प्रहरी के साथ

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Wiki tools

Page tools

Other projects

Hidden categories