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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

स्पीडअप

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

यह भी देखें

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