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

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

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

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

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

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

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

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

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

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

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

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

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

$\lim _{n\rightarrow \infty }{\frac {t(n)}{b(n)}}<\infty .$

ध्यान दें कि यह सीमा, यदि मौजूद है, तो हमेशा कम से कम 1 होती है, क्योंकि t(n) ≥ b(n)।

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

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

स्पीडअप

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

यह भी देखें

• तत्व विशिष्टता समस्या
• एसिम्प्टोटिक कम्प्यूटेशनल जटिलता