Recursive एल्गोरिदम कंप्यूटर विज्ञान में एक मूलभूत अवधारणा है। वे उन्हें छोटे, समान सबप्रोब्लेम में तोड़कर समस्याओं को हल करते हैं। उनकी समय जटिलता को समझना उनकी दक्षता और प्रदर्शन का मूल्यांकन करने में मदद करता है।

समय जटिलता क्या है?

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

Recursive Algorithms

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

गणना के लिए सामान्य तरीके

दो प्राथमिक तरीकों का उपयोग पुनरावृत्ति संबंधों को हल करने के लिए किया जाता है:

  • ]Substitution Method: समाधान का अनुमान लगाएं और इसे प्रेरण के माध्यम से सत्यापित करें।
  • Recursion Tree Method: प्रत्येक स्तर पर लागत को योग देने के लिए एक पेड़ के रूप में पुनरावृत्ति को दृश्यित करें।

उदाहरण के लिए, पुनरावृत्ति टी (एन) = 2T (n/2) + n एक लाभांश-और-conquer एल्गोरिदम का वर्णन करता है। इसको हल करने से ओ (n log n) की समय-सामाजिकता उत्पन्न होती है।