असम्बद्ध रूप से इष्टतम एल्गोरिदम: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Measure of algorithm performance for large inputs}} {{Refimprove|date=October 2008}} कंप्यूटर विज्ञान में, एक...")
 
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Measure of algorithm performance for large inputs}}
{{Short description|Measure of algorithm performance for large inputs}}[[कंप्यूटर विज्ञान]] में, एक [[कलन विधि|एल्गोरिथ्म विधि]] को '''असम्बद्ध रूप से इष्टतम एल्गोरिदम''' कहा जाता है, यदि समान्य रूप से कहें तो, बड़े इनपुट के लिए यह सर्वोत्तम संभव एल्गोरिदम की तुलना में सबसे अच्छा, सबसे व्यर्थ और औसत स्थिति में एक स्थिर कारक (इनपुट आकार से स्वतंत्र) व्यर्थ प्रदर्शन करता है। यह [[ बिग-ओ संकेतन |बिग-ओ संकेतन]] के व्यापक उपयोग के परिणामस्वरूप कंप्यूटर विज्ञान अनुसंधान में समान्यत: सामने आने वाला शब्द है।
{{Refimprove|date=October 2008}}


[[कंप्यूटर विज्ञान]] में, एक [[कलन विधि]] को असम्बद्ध रूप से इष्टतम कहा जाता है, यदि मोटे तौर पर कहें तो, बड़े इनपुट के लिए यह सर्वोत्तम संभव एल्गोरिदम की तुलना में सबसे अच्छा, सबसे खराब और औसत मामले में एक स्थिर कारक (इनपुट आकार से स्वतंत्र) खराब प्रदर्शन करता है। यह [[ बिग-ओ संकेतन ]] के व्यापक उपयोग के परिणामस्वरूप कंप्यूटर विज्ञान अनुसंधान में आमतौर पर सामने आने वाला शब्द है।
अधिक औपचारिक रूप से, एक एल्गोरिथ्म किसी विशेष संसाधन के संबंध में असम्बद्ध रूप से इष्टतम है यदि समस्या के लिए उस संसाधन की Ω(''f''(''n'')) की आवश्यकता सिद्ध हो गई है, और एल्गोरिदम केवल O(''f''(''n'')). का उपयोग करने के लिए सिद्ध हो गया है।


अधिक औपचारिक रूप से, यदि समस्या की आवश्यकता साबित हो गई है तो एक एल्गोरिदम किसी विशेष [[सिस्टम संसाधन]] के संबंध में असम्बद्ध रूप से इष्टतम है {{math|Ω(''f''(''n''))}} उस संसाधन का, और एल्गोरिथ्म केवल उपयोग के लिए सिद्ध हुआ है {{math|O(''f''(''n'')).}}
इन प्रमाणों के लिए गणना के एक विशेष मॉडल की धारणा की आवश्यकता होती है, अथार्त इनपुट डेटा के साथ स्वीकार्य संचालन पर कुछ प्रतिबंध है ।


इन प्रमाणों के लिए गणना के एक विशेष मॉडल की धारणा की आवश्यकता होती है, यानी, इनपुट डेटा के साथ स्वीकार्य संचालन पर कुछ प्रतिबंध।
एक सरल उदाहरण के रूप में, यह ज्ञात है कि सभी तुलना प्रकारों के लिए औसत और सबसे व्यर्थ स्थिति में कम से कम {{math|Ω(''n'' log ''n'')}} तुलना की आवश्यकता होती है। मर्जसॉर्ट और हीपसॉर्ट तुलनात्मक प्रकार हैं जो {{math|O(''n'' log ''n'')}} तुलना करते हैं, इसलिए वे इस अर्थ में स्पर्शोन्मुख रूप से इष्टतम हैं।


एक सरल उदाहरण के रूप में, यह ज्ञात है कि सभी तुलना प्रकारों के लिए कम से कम आवश्यकता होती है {{math|Ω(''n'' log ''n'')}} औसत और सबसे खराब स्थिति में तुलना। मर्ज सॉर्ट और हीप सॉर्ट तुलनात्मक प्रकार हैं जो प्रदर्शन करते हैं {{math|O(''n'' log ''n'')}} तुलना, इसलिए वे इस अर्थ में स्पर्शोन्मुख रूप से इष्टतम हैं।
यदि इनपुट डेटा में कुछ प्राथमिक गुण हैं जिनका तुलना के अतिरिक्त , एल्गोरिदम के निर्माण में उपयोग किया जा सकता है, तो एसिम्प्टोटिक रूप से तेज़ एल्गोरिदम संभव हो सकते हैं। उदाहरण के लिए, यदि यह ज्ञात है कि {{mvar|N}} ऑब्जेक्ट श्रेणी {{math|[1, ''N''],}} से पूर्णांक हैं, तो उन्हें {{math|O(''N'')}} समय पर क्रमबद्ध किया जा सकता है, उदाहरण के लिए, बकेट सॉर्ट द्वारा।                                                                                                                                     


यदि इनपुट डेटा में कुछ प्राथमिकता और पश्च गुण हैं जिनका उपयोग तुलना के अलावा एल्गोरिदम के निर्माण में किया जा सकता है, तो एसिम्प्टोटिक रूप से तेज़ एल्गोरिदम संभव हो सकता है। उदाहरण के लिए, यदि यह ज्ञात हो कि {{mvar|N}} वस्तुएं श्रेणी से [[पूर्णांक]] हैं {{math|[1, ''N''],}} तो उन्हें क्रमबद्ध किया जा सकता है {{math|O(''N'')}} समय, उदाहरण के लिए, बाल्टी क्रम के अनुसार।
किसी एल्गोरिदम के स्पर्शोन्मुख रूप से इष्टतम होने का एक परिणाम यह होता है कि, पर्याप्त बड़े इनपुट के लिए, कोई भी एल्गोरिदम एक स्थिर कारक से अधिक द्वारा उससे उत्तम प्रदर्शन नहीं कर सकता है। इस कारण से, असम्बद्ध रूप से इष्टतम एल्गोरिदम को अधिकांशतः  अनुसंधान में लाइन के अंत के रूप में देखा जाता है, एक ऐसे परिणाम की प्राप्ति जिसमें नाटकीय रूप से सुधार नहीं किया जा सकता है। इसके विपरीत, यदि कोई एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम नहीं है, तो इसका अर्थ है कि जैसे-जैसे इनपुट आकार में बढ़ता है, एल्गोरिदम सर्वोत्तम संभव एल्गोरिदम की तुलना में तेजी से व्यर्थ प्रदर्शन करता है।


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


यद्यपि स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम महत्वपूर्ण सैद्धांतिक परिणाम हैं, एक स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम का उपयोग कई व्यावहारिक स्थितियों में नहीं किया जा सकता है:
यद्यपि स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम महत्वपूर्ण सैद्धांतिक परिणाम हैं, एक स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम का उपयोग कई व्यावहारिक स्थितियों में नहीं किया जा सकता है:
* यह केवल सामान्यतः उपयोग की जाने वाली विधियों से बेहतर प्रदर्शन करता है {{mvar|n}} व्यावहारिक इनपुट आकारों की सीमा से परे, जैसे कि किसी भी [[कंप्यूटर डेटा भंडारण]] में फिट होने से अधिक [[ अंश ]]्स वाले इनपुट।
*यह केवल व्यावहारिक इनपुट आकारों की सीमा से परे n के लिए अधिक सामान्यतः उपयोग किए जाने वाले विधियों से उत्तम प्रदर्शन करता है जैसे कि किसी भी कंप्यूटर स्टोरेज सिस्टम में फिट होने से अधिक बिट्स वाले इनपुट है।
* यह इतना जटिल है कि इसे सही ढंग से समझने और लागू करने की कठिनाई विचाराधीन इनपुट आकारों की सीमा में इसके संभावित लाभ से कहीं अधिक है।
*यह इतना जटिल है कि इसे सही रूप से समझने और प्रयुक्त करने की कठिनाई विचाराधीन इनपुट आकारों की सीमा में इसके संभावित लाभ से कहीं अधिक है।
* व्यवहार में आने वाले इनपुट विशेष मामलों में आते हैं जिनमें अधिक कुशल एल्गोरिदम होते हैं या [[ह्यूरिस्टिक (कंप्यूटर विज्ञान)]] सबसे खराब स्थिति वाले समय को भी कुशलतापूर्वक हल कर सकता है।
* वास्तव में आने वाले इनपुट विशेष स्थिति में आते हैं जिनमें अधिक कुशल एल्गोरिदम होते हैं या [[ह्यूरिस्टिक (कंप्यूटर विज्ञान)]] सबसे व्यर्थ स्थिति वाले समय को भी कुशलतापूर्वक हल कर सकता है।
* आधुनिक कंप्यूटरों पर, [[मेमोरी कैश]] और [[समानांतर कंप्यूटिंग]] जैसे [[कंप्यूटर हार्डवेयर]] अनुकूलन को एक एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम द्वारा तोड़ा जा सकता है (यह मानते हुए कि विश्लेषण ने इन हार्डवेयर अनुकूलन को ध्यान में नहीं रखा है)। इस मामले में, उप-इष्टतम एल्गोरिदम हो सकते हैं जो इन सुविधाओं का बेहतर उपयोग करते हैं और यथार्थवादी डेटा पर एक इष्टतम एल्गोरिदम से बेहतर प्रदर्शन करते हैं।
* आधुनिक कंप्यूटरों पर, [[मेमोरी कैश]] और [[समानांतर कंप्यूटिंग]] जैसे [[कंप्यूटर हार्डवेयर]] अनुकूलन को एक एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम द्वारा तोड़ा जा सकता है (यह मानते हुए कि विश्लेषण ने इन हार्डवेयर अनुकूलन को ध्यान में नहीं रखा है)। इस स्थिति में, उप-इष्टतम एल्गोरिदम हो सकते हैं जो इन सुविधाओं का उत्तम उपयोग करते हैं और यथार्थवादी डेटा पर एक इष्टतम एल्गोरिदम से उत्तम प्रदर्शन करते हैं।


व्यवहार में उपयोग नहीं किए जाने वाले स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम का एक उदाहरण एक साधारण बहुभुज के [[बहुभुज त्रिभुज]] के लिए [[बर्नार्ड चेज़ेल]] का रैखिक-समय एल्गोरिदम है। दूसरा, इष्टतम समय और स्थान में आकार बदलने योग्य सारणी में प्रकाशित [[आकार बदलने योग्य सरणी]] डेटा संरचना है,<ref>{{Citation
वास्तव में उपयोग नहीं किए जाने वाले स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम का एक उदाहरण एक साधारण बहुभुज के [[बहुभुज त्रिभुज]] के लिए [[बर्नार्ड चेज़ेल]] का रैखिक-समय एल्गोरिदम है। दूसरा इष्टतम समय और स्थान में आकार बदलने योग्य सारणी में प्रकाशित [[आकार बदलने योग्य सरणी]] डेटा संरचना है,<ref>{{Citation
| title=Resizable Arrays in Optimal Time and Space
| title=Resizable Arrays in Optimal Time and Space
| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
Line 38: Line 35:
| author3-link=Robert Sedgewick (computer scientist)
| author3-link=Robert Sedgewick (computer scientist)
| publisher=Department of Computer Science, University of Waterloo
| publisher=Department of Computer Science, University of Waterloo
}}</ref> जो निरंतर समय में अनुक्रमित कर सकता है लेकिन कई मशीनों पर सामान्य सरणी अनुक्रमण की तुलना में भारी व्यावहारिक जुर्माना लगता है।
}}</ref> जो निरंतर समय में अनुक्रमित कर सकता है किंतु कई मशीनों पर सामान्य सरणी अनुक्रमण की तुलना में भारी व्यावहारिक जुर्माना लगता है।


==औपचारिक परिभाषाएँ==
==औपचारिक परिभाषाएँ==
औपचारिक रूप से, मान लें कि हमारे पास एक निम्न-सीमा वाला प्रमेय है जो दर्शाता है कि किसी समस्या को आकार n के उदाहरण (इनपुट) के लिए हल करने के लिए Ω(f(n)) समय की आवश्यकता होती है (बिग-ओ नोटेशन#अन्य मानक कंप्यूटर विज्ञान नोटेशन देखें: Ω, ω, Θ, O, o, Õ, ∼|Ω की परिभाषा के लिए बिग-ओ नोटेशन)। फिर, एक एल्गोरिथ्म जो O(f(n)) समय में समस्या का समाधान करता है, उसे स्पर्शोन्मुख रूप से इष्टतम कहा जाता है। इसे सीमाओं का उपयोग करके भी व्यक्त किया जा सकता है: मान लीजिए कि b(n) रनिंग टाइम पर निचली सीमा है, और दिए गए एल्गोरिदम में t(n) समय लगता है। तब एल्गोरिथ्म असम्बद्ध रूप से इष्टतम है यदि:
औपचारिक रूप से, मान लें कि हमारे पास एक निचली सीमा वाला प्रमेय है जो दर्शाता है कि किसी समस्या को आकार n के उदाहरण (इनपुट) के लिए हल करने के लिए Ω(f(n)) समय की आवश्यकता होती है (Ω की परिभाषा के लिए बिग-ओ नोटेशन देखें) फिर, एक एल्गोरिथ्म जो O(f(n)) समय में समस्या का समाधान करता है, उसे स्पर्शोन्मुख रूप से इष्टतम कहा जाता है। इसे सीमाओं का उपयोग करके भी व्यक्त किया जा सकता है: मान लीजिए कि b(n) रनिंग टाइम पर निचली सीमा है, और दिए गए एल्गोरिदम में t(n) समय लगता है। तब एल्गोरिथ्म असम्बद्ध रूप से इष्टतम है यदि:


:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>
:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>
ध्यान दें कि यह सीमा, यदि मौजूद है, तो हमेशा कम से कम 1 होती है, क्योंकि t(n) ≥ b(n)।
ध्यान दें कि यह सीमा, यदि उपस्थित है, सदैव  t(n) ≥ b(n) के रूप में कम से कम 1 होती है।


यद्यपि आमतौर पर समय दक्षता के लिए लागू किया जाता है, एक एल्गोरिदम को एसिम्प्टोटिक रूप से इष्टतम स्थान, यादृच्छिक बिट्स, प्रोसेसर की संख्या, या किसी अन्य संसाधन का उपयोग करने के लिए कहा जा सकता है जिसे आमतौर पर बिग-ओ नोटेशन का उपयोग करके मापा जाता है।
यद्यपि समान्यत: समय दक्षता के लिए प्रयुक्त किया जाता है एक एल्गोरिदम को एसिम्प्टोटिक रूप से इष्टतम स्थान यादृच्छिक बिट्स प्रोसेसर की संख्या, या किसी अन्य संसाधन का उपयोग करने के लिए कहा जा सकता है जिसे समान्यत: बिग-ओ नोटेशन का उपयोग करके मापा जाता है।


कभी-कभी अस्पष्ट या अंतर्निहित धारणाएँ यह अस्पष्ट बना सकती हैं कि क्या कोई एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम है। उदाहरण के लिए, एक निचली सीमा वाला प्रमेय एक विशेष [[अमूर्त मशीन]] मॉडल मान सकता है, जैसा कि तुलना प्रकार या स्मृति के एक विशेष संगठन के मामले में होता है। इन मान्यताओं का उल्लंघन करके, एक नया एल्गोरिदम संभावित रूप से निचली सीमा और एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम से बेहतर प्रदर्शन कर सकता है।
कभी-कभी अस्पष्ट या अंतर्निहित धारणाएँ यह अस्पष्ट बना सकती हैं कि क्या कोई एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम है। उदाहरण के लिए, एक निचली सीमा वाला प्रमेय एक विशेष [[अमूर्त मशीन|एब्स्ट्रेक्ट मशीन]] मॉडल मान सकता है, जैसा कि तुलना प्रकार या मेमोरी के एक विशेष संगठन के स्थिति में होता है। इन मान्यताओं का उल्लंघन करके, एक नया एल्गोरिदम संभावित रूप से निचली सीमा और एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम से उत्तम प्रदर्शन कर सकता है।


==स्पीडअप==
==स्पीडअप==
एक स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम की गैर-मौजूदगी को स्पीडअप कहा जाता है। ब्लम के स्पीडअप प्रमेय से पता चलता है कि स्पीडअप के साथ कृत्रिम रूप से निर्मित समस्याएं मौजूद हैं। हालाँकि, यह एक [[खुली समस्या]] है कि क्या आज के कई सबसे प्रसिद्ध एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम हैं या नहीं। उदाहरण के लिए, वहाँ एक है <math>O(n\alpha(n))</math> न्यूनतम फैले हुए पेड़ों को खोजने के लिए एल्गोरिदम, जहां <math>\alpha(n)</math> [[एकरमैन फ़ंक्शन]] का बहुत धीरे-धीरे बढ़ने वाला उलटा है, लेकिन सबसे अच्छी ज्ञात निचली सीमा तुच्छ है <math>\Omega(n)</math>. क्या यह एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम है यह अज्ञात है, और यदि इसे किसी भी तरह से हल किया गया तो इसे एक महत्वपूर्ण परिणाम के रूप में स्वीकार किए जाने की संभावना होगी। कॉपरस्मिथ और विनोग्राड (1982) ने साबित किया कि मैट्रिक्स गुणन में एल्गोरिदम के एक प्रतिबंधित वर्ग (लैम्ब्डा-गणना के साथ स्ट्रैसेन-प्रकार बिलिनियर पहचान) के बीच गति-गति का एक कमजोर रूप है।
एक स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम की गैर-उपस्थिति  को स्पीडअप कहा जाता है। ब्लम के स्पीडअप प्रमेय से पता चलता है कि स्पीडअप के साथ कृत्रिम रूप से निर्मित समस्याएं उपस्थित हैं। चूँकि, यह एक विवर्त  समस्या है कि क्या आज के कई सबसे प्रसिद्ध एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम हैं या नहीं। उदाहरण के लिए, न्यूनतम फैले हुए पेड़ों को खोजने के लिए एक <math>O(n\alpha(n))</math>एल्गोरिदम है, जहां <math>\alpha(n)</math> एकरमैन फ़ंक्शन का बहुत धीरे-धीरे बढ़ने वाला व्युत्क्रम है, किंतु  सबसे अच्छी ज्ञात निचली सीमा तुच्छ <math>\Omega(n)</math> है। क्या यह एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम है यह अज्ञात है, और यदि इसे किसी भी तरह से हल किया गया तो इसे एक महत्वपूर्ण परिणाम के रूप में स्वीकार किए जाने की संभावना होगी। कॉपरस्मिथ और विनोग्राड (1982) ने सिद्ध किया कि आव्यूह गुणन में एल्गोरिदम के एक प्रतिबंधित वर्ग (लैम्ब्डा-गणना के साथ स्ट्रैसेन-प्रकार बिलिनियर पहचान) के बीच गति-गति का एक अशक्त रूप है।


==यह भी देखें==
==यह भी देखें                                                                                                                                             ==
*[[तत्व विशिष्टता समस्या]]
*[[तत्व विशिष्टता समस्या]]
*एसिम्प्टोटिक कम्प्यूटेशनल जटिलता
*एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्सिटी


==संदर्भ==
==संदर्भ==


{{Reflist}}
{{Reflist}}
[[Category: एल्गोरिदम का विश्लेषण]]


[[Category: Machine Translated Page]]
[[Category:Created On 24/07/2023]]
[[Category:Created On 24/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एल्गोरिदम का विश्लेषण]]

Latest revision as of 16:33, 1 August 2023

कंप्यूटर विज्ञान में, एक एल्गोरिथ्म विधि को असम्बद्ध रूप से इष्टतम एल्गोरिदम कहा जाता है, यदि समान्य रूप से कहें तो, बड़े इनपुट के लिए यह सर्वोत्तम संभव एल्गोरिदम की तुलना में सबसे अच्छा, सबसे व्यर्थ और औसत स्थिति में एक स्थिर कारक (इनपुट आकार से स्वतंत्र) व्यर्थ प्रदर्शन करता है। यह बिग-ओ संकेतन के व्यापक उपयोग के परिणामस्वरूप कंप्यूटर विज्ञान अनुसंधान में समान्यत: सामने आने वाला शब्द है।

अधिक औपचारिक रूप से, एक एल्गोरिथ्म किसी विशेष संसाधन के संबंध में असम्बद्ध रूप से इष्टतम है यदि समस्या के लिए उस संसाधन की Ω(f(n)) की आवश्यकता सिद्ध हो गई है, और एल्गोरिदम केवल O(f(n)). का उपयोग करने के लिए सिद्ध हो गया है।

इन प्रमाणों के लिए गणना के एक विशेष मॉडल की धारणा की आवश्यकता होती है, अथार्त इनपुट डेटा के साथ स्वीकार्य संचालन पर कुछ प्रतिबंध है ।

एक सरल उदाहरण के रूप में, यह ज्ञात है कि सभी तुलना प्रकारों के लिए औसत और सबसे व्यर्थ स्थिति में कम से कम Ω(n log n) तुलना की आवश्यकता होती है। मर्जसॉर्ट और हीपसॉर्ट तुलनात्मक प्रकार हैं जो O(n log n) तुलना करते हैं, इसलिए वे इस अर्थ में स्पर्शोन्मुख रूप से इष्टतम हैं।

यदि इनपुट डेटा में कुछ प्राथमिक गुण हैं जिनका तुलना के अतिरिक्त , एल्गोरिदम के निर्माण में उपयोग किया जा सकता है, तो एसिम्प्टोटिक रूप से तेज़ एल्गोरिदम संभव हो सकते हैं। उदाहरण के लिए, यदि यह ज्ञात है कि N ऑब्जेक्ट श्रेणी [1, N], से पूर्णांक हैं, तो उन्हें O(N) समय पर क्रमबद्ध किया जा सकता है, उदाहरण के लिए, बकेट सॉर्ट द्वारा।

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

वास्तव में ऐसे एल्गोरिदम खोजना उपयोगी है जो उत्तम प्रदर्शन करते हैं, तथापि उन्हें कोई स्पर्शोन्मुख लाभ न मिले। नए एल्गोरिदम विशिष्ट इनपुट पर उत्तम प्रदर्शन, संसाधनों का कम उपयोग, या वर्णन और कार्यान्वयन में सरल होने जैसे लाभ भी प्रस्तुत कर सकते हैं। इस प्रकार स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम सदैव पंक्ति का अंत नहीं होते हैं।

यद्यपि स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम महत्वपूर्ण सैद्धांतिक परिणाम हैं, एक स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम का उपयोग कई व्यावहारिक स्थितियों में नहीं किया जा सकता है:

  • यह केवल व्यावहारिक इनपुट आकारों की सीमा से परे n के लिए अधिक सामान्यतः उपयोग किए जाने वाले विधियों से उत्तम प्रदर्शन करता है जैसे कि किसी भी कंप्यूटर स्टोरेज सिस्टम में फिट होने से अधिक बिट्स वाले इनपुट है।
  • यह इतना जटिल है कि इसे सही रूप से समझने और प्रयुक्त करने की कठिनाई विचाराधीन इनपुट आकारों की सीमा में इसके संभावित लाभ से कहीं अधिक है।
  • वास्तव में आने वाले इनपुट विशेष स्थिति में आते हैं जिनमें अधिक कुशल एल्गोरिदम होते हैं या ह्यूरिस्टिक (कंप्यूटर विज्ञान) सबसे व्यर्थ स्थिति वाले समय को भी कुशलतापूर्वक हल कर सकता है।
  • आधुनिक कंप्यूटरों पर, मेमोरी कैश और समानांतर कंप्यूटिंग जैसे कंप्यूटर हार्डवेयर अनुकूलन को एक एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम द्वारा तोड़ा जा सकता है (यह मानते हुए कि विश्लेषण ने इन हार्डवेयर अनुकूलन को ध्यान में नहीं रखा है)। इस स्थिति में, उप-इष्टतम एल्गोरिदम हो सकते हैं जो इन सुविधाओं का उत्तम उपयोग करते हैं और यथार्थवादी डेटा पर एक इष्टतम एल्गोरिदम से उत्तम प्रदर्शन करते हैं।

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

औपचारिक परिभाषाएँ

औपचारिक रूप से, मान लें कि हमारे पास एक निचली सीमा वाला प्रमेय है जो दर्शाता है कि किसी समस्या को आकार n के उदाहरण (इनपुट) के लिए हल करने के लिए Ω(f(n)) समय की आवश्यकता होती है (Ω की परिभाषा के लिए बिग-ओ नोटेशन देखें) फिर, एक एल्गोरिथ्म जो O(f(n)) समय में समस्या का समाधान करता है, उसे स्पर्शोन्मुख रूप से इष्टतम कहा जाता है। इसे सीमाओं का उपयोग करके भी व्यक्त किया जा सकता है: मान लीजिए कि b(n) रनिंग टाइम पर निचली सीमा है, और दिए गए एल्गोरिदम में t(n) समय लगता है। तब एल्गोरिथ्म असम्बद्ध रूप से इष्टतम है यदि:

ध्यान दें कि यह सीमा, यदि उपस्थित है, सदैव t(n) ≥ b(n) के रूप में कम से कम 1 होती है।

यद्यपि समान्यत: समय दक्षता के लिए प्रयुक्त किया जाता है एक एल्गोरिदम को एसिम्प्टोटिक रूप से इष्टतम स्थान यादृच्छिक बिट्स प्रोसेसर की संख्या, या किसी अन्य संसाधन का उपयोग करने के लिए कहा जा सकता है जिसे समान्यत: बिग-ओ नोटेशन का उपयोग करके मापा जाता है।

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

स्पीडअप

एक स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम की गैर-उपस्थिति को स्पीडअप कहा जाता है। ब्लम के स्पीडअप प्रमेय से पता चलता है कि स्पीडअप के साथ कृत्रिम रूप से निर्मित समस्याएं उपस्थित हैं। चूँकि, यह एक विवर्त समस्या है कि क्या आज के कई सबसे प्रसिद्ध एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम हैं या नहीं। उदाहरण के लिए, न्यूनतम फैले हुए पेड़ों को खोजने के लिए एक एल्गोरिदम है, जहां एकरमैन फ़ंक्शन का बहुत धीरे-धीरे बढ़ने वाला व्युत्क्रम है, किंतु सबसे अच्छी ज्ञात निचली सीमा तुच्छ है। क्या यह एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम है यह अज्ञात है, और यदि इसे किसी भी तरह से हल किया गया तो इसे एक महत्वपूर्ण परिणाम के रूप में स्वीकार किए जाने की संभावना होगी। कॉपरस्मिथ और विनोग्राड (1982) ने सिद्ध किया कि आव्यूह गुणन में एल्गोरिदम के एक प्रतिबंधित वर्ग (लैम्ब्डा-गणना के साथ स्ट्रैसेन-प्रकार बिलिनियर पहचान) के बीच गति-गति का एक अशक्त रूप है।

यह भी देखें

संदर्भ

  1. ↑ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=असम्बद्ध_रूप_से_इष्टतम_एल्गोरिदम&oldid=232857’