डिवाइड एंड कॉनकॉट रिलैप्स के लिए उन्नत मास्टर प्रमेय

फूट डालो और जीतो एक एल्गोरिथ्म है जो समान प्रकार की कई उप-समस्याओं में पुनरावर्ती रूप से शाखाओं में बंटी समस्या पर आधारित प्रतिमान पर काम करता है जिसे आसानी से हल किया जा सकता है।

उदाहरण

आइए फूट डालो और जीतो तकनीक के बारे में अधिक जानने के लिए एक उदाहरण लेते हैं -

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

सभी उपसमस्याओं के परिणामों को मिलाएं और मूल समस्या का समाधान लौटाएं।

स्पष्टीकरण - उपरोक्त समस्या में, समस्या सेट को छोटे उप-समस्याओं में विभाजित किया जाना है जिन्हें आसानी से हल किया जा सकता है।

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

उपरोक्त उदाहरण में समस्या के रनटाइम मान का उदाहरण -

T(n) = f(n) + m.T(n/p)

अधिकांश रिकर्सिव एल्गोरिदम के लिए, आप मास्टर के प्रमेय का उपयोग करके एल्गोरिदम के लिए समय जटिलता ढूंढने में सक्षम होंगे, लेकिन कुछ मामलों में मास्टर का प्रमेय लागू नहीं हो सकता है। ये वे मामले हैं जिनमें मास्टर प्रमेय लागू नहीं होता है। जब समस्या T(n) मोनोटोन नहीं है, उदाहरण के लिए, T(n) =sin n। समस्या फलन f(n) एक बहुपद नहीं है।

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

T(n) = aT(n/b) + ø((n^k)logpn)

जहाँ n समस्या का आकार है।

a =पुनरावृत्ति में उपसमस्याओं की संख्या, a> 0

n/b =प्रत्येक उपसमस्या का आकार b> 1, k>=0 और p एक वास्तविक संख्या है।

इस प्रकार की समस्या को हल करने के लिए, हम निम्नलिखित समाधानों का उपयोग करेंगे,

• अगर ए>बी<उप>के , तब T(n) =(nlogba)
• अगर ए =बी<उप>के , फिर
  • यदि p> -1, तो T(n) =∅(nlogba log ^p+1 एन)
  • यदि p =-1, तो T(n) =∅(nlog_ba लॉगलॉगन)
  • यदि p <-1, तो T(n) =∅(nlog_ba )
• अगर एकके , फिर
  • यदि p> =0, तो T(n)=∅(n_k लॉग <उप>पी एन)
  • यदि p<0, तो T(n) =∅(nk)

उन्नत मास्टर एल्गोरिथम का उपयोग करके, हम कुछ एल्गोरिदम की जटिलता की गणना करेंगे -

द्विआधारी खोज - t(n) =θ(logn)

मर्ज सॉर्ट करें - टी(एन) =θ(nlogn)