एल्गोरिदम की जटिलता और विश्लेषण

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

Definition

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

Scope

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

Sub-topics

• अमूर्त विश्लेषण
• एसिम्प्टोटिक विश्लेषण
• एनपी-पूर्णता और असाध्यता
• पुनरावृत्ति संबंध

Core questions

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

Key concepts

• बिग-ओ, बिग-ओमेगा, बिग-थीटा
• सबसे खराब स्थिति और औसत स्थिति विश्लेषण
• पुनरावृत्ति संबंध
• मास्टर प्रमेय
• अमोर्तिज़ेड विश्लेषण
• निचली सीमाएं
• बहुपद समय
• एनपी-पूर्णता

Key theories

एसिम्प्टोटिक नोटेशन

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

व्यवहार्यता और एनपी-पूर्णता

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

Clinical relevance

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

History

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

Debates

पी बनाम एनपी

क्या हर समस्या जिसके समाधानों को जल्दी से सत्यापित किया जा सकता है, उसे भी जल्दी से हल किया जा सकता है (पी = एनपी) सैद्धांतिक कंप्यूटर विज्ञान का केंद्रीय खुला प्रश्न है; यह व्यापक रूप से अनुमान लगाया गया है कि पी एनपी के बराबर नहीं है, लेकिन कोई प्रमाण मौजूद नहीं है।

Key figures

• Donald Knuth
• Stephen Cook
• Richard Karp
• Robert Tarjan

Seminal works

• cormen2009
• knuth1976bigo
• kleinberg2006

Frequently asked questions

सबसे खराब स्थिति और औसत स्थिति विश्लेषण में क्या अंतर है?

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

यदि कोई समस्या एनपी-पूर्ण है, तो क्या इसे हल करना निराशाजनक है?

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