पुनरावृत्ति संबंध
पुनरावृत्ति संबंध एक पुनरावर्ती एल्गोरिथम के चलने के समय को छोटे इनपुट पर उसके चलने के समय के संदर्भ में व्यक्त करते हैं; इन्हें हल करने से क्लोज्ड-फॉर्म एसिम्प्टोटिक बाउंड्स प्राप्त होते हैं जिनका उपयोग डिवाइड-एंड-कॉन्कर और अन्य पुनरावर्ती एल्गोरिथम का विश्लेषण करने के लिए किया जाता है।
Definition
एक पुनरावृत्ति संबंध एक समीकरण है जो एक फ़ंक्शन के मान को छोटे इनपुट पर उसके मानों के संदर्भ में परिभाषित करता है; एल्गोरिथम विश्लेषण में, यह n आकार के इनपुट पर एक एल्गोरिथम की लागत को छोटे उपसमस्याओं पर उसकी लागत के संदर्भ में व्यक्त करता है।
Scope
यह विषय एल्गोरिथम विश्लेषण में उत्पन्न होने वाली पुनरावृत्तियों के निरूपण और समाधान को शामिल करता है: प्रतिस्थापन विधि, पुनरावर्तन-वृक्ष विधि, और T(n) = aT(n/b) + f(n) के रूप में डिवाइड-एंड-कॉन्कर पुनरावृत्तियों के लिए मास्टर प्रमेय। यह बताता है कि प्रत्येक पुनरावर्ती एल्गोरिथम कैसे एक पुनरावृत्ति को प्रेरित करता है और उस पुनरावृत्ति को बिग-थीटा बाउंड में कैसे अनुवादित किया जाए। इसमें एसिम्प्टोटिक नोटेशन स्वयं शामिल नहीं है, जिसे अलग से माना जाता है, और असतत गणित से कॉम्बिनेटरियल जनरेटिंग-फंक्शन विधियाँ भी शामिल नहीं हैं।
Core questions
- एक पुनरावर्ती एल्गोरिथम अपने चलने के समय के लिए पुनरावृत्ति को कैसे जन्म देता है?
- अनुमानित समाधान को सिद्ध करने और सत्यापित करने के लिए प्रतिस्थापन विधि का उपयोग कैसे किया जाता है?
- पुनरावर्तन-वृक्ष विधि पुनरावर्तन स्तरों पर किए गए कुल कार्य को कैसे उजागर करती है?
- मास्टर प्रमेय कब लागू होता है, और इसके तीन मामलों का क्या अर्थ है?
- मास्टर प्रमेय के रूप से बाहर आने वाली पुनरावृत्तियों को कैसे संभाला जाता है?
Key concepts
- पुनरावृत्ति संबंध
- प्रतिस्थापन विधि
- पुनरावर्तन-वृक्ष विधि
- मास्टर प्रमेय
- डिवाइड-एंड-कॉन्कर पुनरावृत्ति
- आधार स्थिति और पुनरावर्ती स्थिति
- क्लोज्ड-फॉर्म समाधान
- अकरा-बाज़ी विधि
Key theories
- मास्टर प्रमेय
- डिवाइड-एंड-कॉन्कर पुनरावृत्तियों T(n) = aT(n/b) + f(n) के लिए, मास्टर प्रमेय f(n) की तुलना n की घात log base b of a से करके एसिम्प्टोटिक समाधान देता है, जिसमें तीन मामले शामिल हैं जहाँ लीव्स, रूट, या संतुलित स्तर हावी होते हैं।
- पुनरावर्तन-वृक्ष और प्रतिस्थापन विधियाँ
- पुनरावर्तन-वृक्ष विधि पुनरावर्तन के प्रत्येक स्तर पर किए गए कार्य को जोड़कर एक बाउंड का सुझाव देती है, जिसे प्रतिस्थापन विधि फिर प्रेरण द्वारा कठोरता से सिद्ध करती है; साथ में वे मास्टर प्रमेय के दायरे से परे पुनरावृत्तियों को संभालते हैं।
Clinical relevance
पुनरावृत्ति समाधान पुनरावर्ती एल्गोरिथम के चलने के समय का मानक मार्ग है, मर्जसॉर्ट और क्विकसॉर्ट से लेकर तेज़ गुणन और कई डायनेमिक प्रोग्राम तक। इंजीनियर और शोधकर्ता ऐसे एल्गोरिथम से जुड़े एसिम्प्टोटिक जटिलता दावों को प्राप्त करने और न्यायोचित ठहराने के लिए नियमित रूप से मास्टर प्रमेय का उपयोग करते हैं।
History
एल्गोरिथम का पुनरावृत्ति विश्लेषण नुथ की 'द आर्ट ऑफ कंप्यूटर प्रोग्रामिंग' में व्यवस्थित किया गया था। मास्टर प्रमेय CLRS के माध्यम से एक पाठ्यपुस्तक का मुख्य आधार बन गया, और अकरा-बाज़ी विधि (1998) ने इसे असमान विभाजन के साथ डिवाइड-एंड-कॉन्कर पुनरावृत्तियों के एक व्यापक वर्ग के लिए सामान्यीकृत किया।
Key figures
- Donald Knuth
- Mohamad Akra
- Louay Bazzi
Related topics
Seminal works
- cormen2009
- knuth1997vol1
Frequently asked questions
- मैं मास्टर प्रमेय का उपयोग कब कर सकता हूँ?
- मास्टर प्रमेय T(n) = aT(n/b) + f(n) के रूप में a >= 1 और b > 1 के साथ पुनरावृत्तियों पर लागू होता है, जहाँ प्रत्येक स्तर समस्या को n/b आकार के a उपसमस्याओं में विभाजित करता है। असमान विभाजन, भिन्न उपसमस्या आकार, या गैर-बहुपद संयोजन लागत वाली पुनरावृत्तियों को इसके बजाय पुनरावर्तन-वृक्ष, प्रतिस्थापन, या अकरा-बाज़ी विधियों की आवश्यकता हो सकती है।
- मर्जसॉर्ट की पुनरावृत्ति O(n log n) क्यों देती है?
- मर्जसॉर्ट T(n) = 2T(n/2) + O(n) देता है: दो आधे आकार की उपसमस्याएँ और रैखिक विलय। यहाँ प्रति-स्तर का कार्य पुनरावर्तन वृक्ष के सभी log n स्तरों पर समान है, इसलिए कुल n गुना log n है, जिसे मास्टर प्रमेय Theta(n log n) के रूप में पुष्टि करता है।