गतिशील प्रोग्रामिंग के साथ हर रिकर्सिव एल्गोरिदम में सुधार किया जा सकता है?

Question

मैं एक प्रथम वर्ष स्नातक सीएससी छात्र हूं जो प्रतिस्पर्धी प्रोग्रामिंग में शामिल होने की तलाश में है।

रिकर्सन में उप समस्याओं को परिभाषित करना और हल करना शामिल है। जैसा कि मैं समझता हूं, शीर्ष गतिशील प्रोग्रामिंग (डीपी) में एल्गोरिदम की समय जटिलता को कम करने के लिए उप समस्याओं के समाधान को याद करना शामिल है।

उपरोक्त उप समस्याओं के साथ प्रत्येक रिकर्सिव एल्गोरिदम की दक्षता में सुधार करने के लिए डीपी का उपयोग किया जा सकता है? डीपी काम करने में असफल होगा और मैं इसकी पहचान कैसे कर सकता हूं?

Answer 1

संक्षिप्त उत्तर है: हाँ।

हालांकि, कुछ बाधाएं हैं। सबसे स्पष्ट बात यह है कि रिकर्सिव कॉल ओवरलैप होनी चाहिए। अर्थात। एक एल्गोरिदम के निष्पादन के दौरान, रिकर्सिव फ़ंक्शन को एक ही पैरामीटर के साथ कई बार बुलाया जाना चाहिए। यह आपको यादों द्वारा रिकर्सन पेड़ को छोटा करने देता है। तो आप कॉल की संख्या को कम करने के लिए हमेशा यादों का उपयोग कर सकते हैं।

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