रेखीय खोज: 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 14:25, 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$ का $n$ मान या रिकॉर्ड वाले तत्व (कंप्यूटर विज्ञान) $L 0 .... L n -1$ , और लक्ष्य मान $T$ , निम्नलिखित लक्ष्य के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है $T$ में $L$ .^[3]

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

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

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

उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: यह जांचने के लिए कि क्या $L i$ टी के बराबर है, और दूसरा यह जांचने के लिए है $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 तुलना की आवश्यकता होती है।

यदि मांगा जा रहा मूल्य सूची में 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 है, जो एकल if-then-else निर्माण के अनुरूप है)।

किसी भी तरह से, स्पर्शोन्मुख जटिलता सबसे व्यर्थ स्थिति की लागत और रैखिक खोज की अपेक्षित लागत दोनों बड़े ओ अंकन (एन) हैं।

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

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

विशेष रूप से, जब सूची आइटम को घटती संभावना के क्रम में व्यवस्थित किया जाता है, और ये संभावनाएं ज्यामितीय वितरण होती हैं, तो रैखिक खोज की लागत केवल 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''}} का {{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''}} का {{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''}} के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है।
 # तय करना {{math|''i''}} से 0.
@@ Line 41: / Line 43: @@
 ==विश्लेषण==
-एन आइटम वाली सूची के लिए, सबसे अच्छा मामला तब होता है जब मान सूची के पहले तत्व के बराबर होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे खराब स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
+एन आइटम वाली सूची के लिए, सबसे अच्छा  स्तिथि  तब होता है जब मान सूची के पहले तत्व के बराबर होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे व्यर्थ  स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
 यदि मांगा जा रहा मूल्य सूची में k बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है
@@ Line 55: / Line 57: @@
 (उदाहरण के लिए, n = 2 के लिए यह 1 है, जो एकल if-then-else निर्माण के अनुरूप है)।
-किसी भी तरह से, [[स्पर्शोन्मुख जटिलता]] सबसे खराब स्थिति की लागत और रैखिक खोज की अपेक्षित लागत दोनों बड़े ओ अंकन (एन) हैं।
+किसी भी तरह से, [[स्पर्शोन्मुख जटिलता]] सबसे व्यर्थ  स्थिति की लागत और रैखिक खोज की अपेक्षित लागत दोनों बड़े ओ अंकन (एन) हैं।
 ===गैर-समान संभावनाएँ===

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 14:25, 5 July 2023

Contents

एल्गोरिदम

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

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

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 14:25, 5 July 2023

एल्गोरिदम

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

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

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Wiki tools

Page tools

Other projects

Hidden categories