मास्टर प्रमेय (एल्गोरिदम का विश्लेषण): Difference between revisions
No edit summary |
No edit summary |
||
Line 2: | Line 2: | ||
{{For|अन्य प्रमेय जिन्हें ''मास्टर प्रमेय'' कहा जाता है|मास्टर प्रमेय (बहुविकल्पी){{!}}मास्टर प्रमेय}} | {{For|अन्य प्रमेय जिन्हें ''मास्टर प्रमेय'' कहा जाता है|मास्टर प्रमेय (बहुविकल्पी){{!}}मास्टर प्रमेय}} | ||
एल्गोरिदम के विश्लेषण में, विभाजन और जीत पुनरावृत्ति के लिए मास्टर प्रमेय कई विभाजन और जीत एल्गोरिदम के विश्लेषण में होने वाले प्रकार के [[पुनरावृत्ति संबंध|पुनरावृत्ति संबंधों]] के लिए [[स्पर्शोन्मुख विश्लेषण]] ([[बिग ओ नोटेशन]] का उपयोग करके) प्रदान करता है। यह दृष्टिकोण पहली बार 1980 में [[जॉन बेंटले (कंप्यूटर वैज्ञानिक)]], [[डोरोथिया ब्लोस्टीन]] (नी हेकेन) और जेम्स बी सक्से द्वारा प्रस्तुत किया गया था, जहां इसे इस | एल्गोरिदम के विश्लेषण में, विभाजन और जीत पुनरावृत्ति के लिए मास्टर प्रमेय कई विभाजन और जीत एल्गोरिदम के विश्लेषण में होने वाले प्रकार के [[पुनरावृत्ति संबंध|पुनरावृत्ति संबंधों]] के लिए [[स्पर्शोन्मुख विश्लेषण]] ([[बिग ओ नोटेशन]] का उपयोग करके) प्रदान करता है। यह दृष्टिकोण पहली बार 1980 में [[जॉन बेंटले (कंप्यूटर वैज्ञानिक)]], [[डोरोथिया ब्लोस्टीन]] (नी हेकेन) और जेम्स बी सक्से द्वारा प्रस्तुत किया गया था, जहां इसे इस प्रकार की पुनरावृत्ति का समाधान करने के लिए एकीकृत विधि के रूप में वर्णित किया गया था।<ref>{{citation | last1 = Bentley | first1 = Jon Louis | author1-link = Jon Bentley (computer scientist) | last2 = Haken | first2 = Dorothea | author2-link = Dorothea Blostein | last3 = Saxe | first3 = James B. | author3-link = James B. Saxe | date = September 1980 | doi = 10.1145/1008861.1008865 | issue = 3 | journal = [[ACM SIGACT News]] | pages = 36–44 | title = A general method for solving divide-and-conquer recurrences | volume = 12| s2cid = 40642274 | url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 | archive-url = https://web.archive.org/web/20170922231154/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294 | url-status = dead | archive-date = September 22, 2017 }}</ref> मास्टर प्रमेय का नाम व्यापक रूप से उपयोग किए जाने वाले एल्गोरिदम पाठ्यपुस्तक [[एल्गोरिदम का परिचय]] (एल्गोरिदम टेक्स्टबुक इंट्रोडक्शन टू एल्गोरिदम) द्वारा थॉमस एच. कॉर्मेन, चार्ल्स ई. लीसरसन, [[रॉन रिवेस्ट]] और [[क्लिफर्ड स्टीन]] द्वारा लोकप्रिय किया गया था। | ||
इस प्रमेय के उपयोग से सभी पुनरावृत्ति संबंधों को | इस प्रमेय के उपयोग से सभी पुनरावृत्ति संबंधों को समाधान नहीं किया जा सकता है; इसके सामान्यीकरण में अकरा-बाज़ी पद्धति सम्मिलित है। | ||
== परिचय == | == परिचय == | ||
समस्या पर विचार करें जिसे पुनरावर्ती एल्गोरिथम का उपयोग करके | समस्या पर विचार करें जिसे पुनरावर्ती एल्गोरिथम का उपयोग करके समाधान किया जा सकता है जैसे कि निम्नलिखित:<syntaxhighlight lang="d"> | ||
procedure p(input x of size n): | procedure p(input x of size n): | ||
if n < some constant k: | if n < some constant k: | ||
Line 15: | Line 15: | ||
Call procedure p recursively on each subproblem | Call procedure p recursively on each subproblem | ||
Combine the results from the subproblems | Combine the results from the subproblems | ||
</syntaxhighlight>[[File:Recursive_problem_solving.svg|thumb|right|359x359px|समाधान ट्री।]]उपरोक्त कलन विधि समस्या को पुनरावर्ती रूप से कई उप-समस्याओं में विभाजित करता है, प्रत्येक उप-समस्या आकार {{math|''n''/''b''}} की होती है. इसके समाधान के पेड़ में प्रत्येक पुनरावर्ती कॉल के लिए एक नोड होता है, उस नोड के बच्चे उस कॉल से किए गए अन्य कॉल होते हैं। पेड़ की पत्तियां पुनरावर्तन के आधार | </syntaxhighlight>[[File:Recursive_problem_solving.svg|thumb|right|359x359px|समाधान ट्री।]]उपरोक्त कलन विधि समस्या को पुनरावर्ती रूप से कई उप-समस्याओं में विभाजित करता है, प्रत्येक उप-समस्या आकार {{math|''n''/''b''}} की होती है. इसके समाधान के पेड़ में प्रत्येक पुनरावर्ती कॉल के लिए एक नोड होता है, उस नोड के बच्चे उस कॉल से किए गए अन्य कॉल होते हैं। पेड़ की पत्तियां पुनरावर्तन के आधार स्थिति हैं, उप-समस्याएं (के से कम आकार की) जो पुनरावर्तन नहीं करती हैं। उपरोक्त उदाहरण {{mvar|a}} प्रत्येक गैर-पत्ती नोड पर चाइल्ड नोड होगा। प्रत्येक नोड काम की मात्रा करता है जो उप-समस्या {{mvar|n}} के आकार के अनुरूप होता है। पुनरावर्ती कॉल के उस उदाहरण को पास किया गया और इसके <math>f(n)</math> द्वारा दिया गया . संपूर्ण एल्गोरिथम द्वारा किए गए कार्य की कुल राशि ट्री में सभी नोड्स द्वारा किए गए कार्य का योग है। | ||
एल्गोरिथम का रनटाइम जैसे आकार 'n' के इनपुट पर ऊपर 'p', | एल्गोरिथम का रनटाइम जैसे आकार 'n' के इनपुट पर ऊपर 'p', सामान्यतः <math>T(n)</math> द्वारा निरूपित किया जाता है, पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है | ||
:<math>T(n) = a \; T\left(\frac{n}{b}\right) + f(n),</math> | :<math>T(n) = a \; T\left(\frac{n}{b}\right) + f(n),</math> | ||
जहाँ <math> f(n)</math> उपरोक्त प्रक्रिया में उप-समस्याओं को बनाने और उनके परिणामों को संयोजित करने का समय है। किए गए कार्य की कुल राशि के लिए व्यंजक प्राप्त करने के लिए इस समीकरण को क्रमिक रूप से स्वयं में प्रतिस्थापित किया जा सकता है और विस्तारित किया जा सकता है।<ref> | जहाँ <math> f(n)</math> उपरोक्त प्रक्रिया में उप-समस्याओं को बनाने और उनके परिणामों को संयोजित करने का समय है। किए गए कार्य की कुल राशि के लिए व्यंजक प्राप्त करने के लिए इस समीकरण को क्रमिक रूप से स्वयं में प्रतिस्थापित किया जा सकता है और विस्तारित किया जा सकता है।<ref> | ||
Line 27: | Line 27: | ||
== सामान्य रूप == | == सामान्य रूप == | ||
मास्टर प्रमेय हमेशा विभाजित और जीत एल्गोरिदम से पुनरावृत्ति के लिए असम्बद्ध रूप से तंग सीमा उत्पन्न करता है जो इनपुट को समान आकार के छोटे उप-समस्याओं में विभाजित करता है, उप-समस्याओं को पुनरावर्ती रूप से | मास्टर प्रमेय हमेशा विभाजित और जीत एल्गोरिदम से पुनरावृत्ति के लिए असम्बद्ध रूप से तंग सीमा उत्पन्न करता है जो इनपुट को समान आकार के छोटे उप-समस्याओं में विभाजित करता है, उप-समस्याओं को पुनरावर्ती रूप से समाधान करता है, और फिर मूल समस्या का समाधान देने के लिए उप-समस्या समाधानों को जोड़ता है। इस प्रकार के कलन विधि के लिए समय उस कार्य को जोड़कर व्यक्त किया जा सकता है जो वे अपने पुनरावर्तन के शीर्ष स्तर पर (समस्याओं को उप-समस्याओं में विभाजित करने के लिए और फिर उप-समस्याओं के समाधानों को संयोजित करने के लिए) एक साथ कलन विधि के पुनरावर्ती कॉल में किए गए समय के साथ करते हैं। यदि <math>T(n)</math> आकार के इनपुट पर कलन विधि के लिए कुल समय <math>n</math> को दर्शाता है, और <math>f(n)</math> पुनरावृत्ति के शीर्ष स्तर पर लगने वाले समय की मात्रा को दर्शाता है तो समय को पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है जो रूप लेता है: | ||
:<math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)</math> | :<math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)</math> | ||
यहाँ <math>n</math> एक इनपुट समस्या का आकार है, <math>a</math> पुनरावर्तन में उपसमस्याओं की संख्या है, और <math>b</math> वह कारक है जिसके द्वारा प्रत्येक पुनरावर्ती कॉल (b> 1) में उप-समस्या का आकार कम हो जाता है। महत्वपूर्ण रूप से, <math>a</math> और <math>b</math> पर <math>n</math> निर्भर नहीं होना चाहिए. नीचे दिया गया प्रमेय यह भी मानता है कि, पुनरावृत्ति के आधार | यहाँ <math>n</math> एक इनपुट समस्या का आकार है, <math>a</math> पुनरावर्तन में उपसमस्याओं की संख्या है, और <math>b</math> वह कारक है जिसके द्वारा प्रत्येक पुनरावर्ती कॉल (b> 1) में उप-समस्या का आकार कम हो जाता है। महत्वपूर्ण रूप से, <math>a</math> और <math>b</math> पर <math>n</math> निर्भर नहीं होना चाहिए. नीचे दिया गया प्रमेय यह भी मानता है कि, पुनरावृत्ति के आधार स्थिति के रूप में, <math>T(n)=\Theta(1)</math> तब <math>n</math> किसी <math>\kappa > 0</math> सीमा से कम है, सबसे छोटा इनपुट आकार जो पुनरावर्ती कॉल की ओर ले जाएगा। | ||
समस्या को विभाजित/पुन: संयोजित करने के कार्य के आधार पर, इस फ़ॉर्म की पुनरावृत्ति | समस्या को विभाजित/पुन: संयोजित करने के कार्य के आधार पर, इस फ़ॉर्म की पुनरावृत्ति अधिकांश निम्नलिखित तीन शासनों में से एक को संतुष्ट करती है <math>f(n)</math> महत्वपूर्ण घातांक <math>c_{\operatorname{crit}}=\log_b a</math>. (नीचे दी गई तालिका मानक बिग ओ नोटेशन का उपयोग करती है) से संबंधित है। | ||
:<math>c_{\operatorname{crit}} = \log_b a = \log(\#\text{subproblems})/\log(\text{relative subproblem size})</math> | :<math>c_{\operatorname{crit}} = \log_b a = \log(\#\text{subproblems})/\log(\text{relative subproblem size})</math> | ||
Line 39: | Line 39: | ||
! width=10|स्थिति | ! width=10|स्थिति | ||
! विवरण | ! विवरण | ||
! <math>f(n)</math> <math>c_{\operatorname{crit}}</math> के संबंध में, | ! <math>f(n)</math> <math>c_{\operatorname{crit}}</math> के संबंध में, अर्थात्, <math>\log_b a</math> पर स्थिति | ||
! मास्टर प्रमेय बाध्य | ! मास्टर प्रमेय बाध्य | ||
! width=400|सांकेतिक उदाहरण | ! width=400|सांकेतिक उदाहरण | ||
Line 47: | Line 47: | ||
! 1 | ! 1 | ||
| किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं से बौना हो जाता है। | | किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं से बौना हो जाता है। | ||
अर्थात् पुनरावर्तन वृक्ष पत्ती-भारी है | |||
| जब <math>f(n) = O(n^{c})</math> जहाँ <math>c<c_{\operatorname{crit}}</math> | | जब <math>f(n) = O(n^{c})</math> जहाँ <math>c<c_{\operatorname{crit}}</math> | ||
Line 80: | Line 80: | ||
! 3 | ! 3 | ||
| किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं पर हावी हो जाता है। | | किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं पर हावी हो जाता है। | ||
अर्थात् रिकर्सन ट्री रूट-हैवी है। | |||
| जब <math>f(n) = \Omega(n^{c})</math> जहाँ <math>c>c_{\operatorname{crit}}</math> | | जब <math>f(n) = \Omega(n^{c})</math> जहाँ <math>c>c_{\operatorname{crit}}</math> | ||
(अधिक-प्रतिपादक बहुपद द्वारा निम्न-परिबद्ध) | (अधिक-प्रतिपादक बहुपद द्वारा निम्न-परिबद्ध) | ||
| ... यह आवश्यक रूप से कुछ भी नहीं देता है। इसके | | ... यह आवश्यक रूप से कुछ भी नहीं देता है। इसके अतिरिक्त, यदि | ||
:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for कुछ स्थिर <math>k < 1</math> और और काफी बड़ा <math>n</math> ( | :<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for कुछ स्थिर <math>k < 1</math> और और काफी बड़ा <math>n</math> (अधिकांश नियमितता की स्थिति कहा जाता है) | ||
तो कुल बंटवारे की अवधि का प्रभुत्व है <math>f(n)</math>: | तो कुल बंटवारे की अवधि का प्रभुत्व है <math>f(n)</math>: | ||
Line 103: | Line 103: | ||
|- | |- | ||
! width=10|स्थिति | ! width=10|स्थिति | ||
! <math>f(n)</math> <math>c_{\operatorname{crit}}</math> के संबंध में, | ! <math>f(n)</math> <math>c_{\operatorname{crit}}</math> के संबंध में, अर्थात्, <math>\log_b a</math> पर स्थिति | ||
! मास्टर प्रमेय बाध्य | ! मास्टर प्रमेय बाध्य | ||
! width=400|सांकेतिक उदाहरण | ! width=400|सांकेतिक उदाहरण | ||
Line 154: | Line 154: | ||
:<math>\log_b a = \log_2 8 = 3>c</math>. | :<math>\log_b a = \log_2 8 = 3>c</math>. | ||
यह मास्टर प्रमेय के पहले | यह मास्टर प्रमेय के पहले स्थिति से अनुसरण करता है | ||
:<math>T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)</math> | :<math>T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)</math> | ||
Line 169: | Line 169: | ||
:<math>\log_b a = \log_2 2 = 1</math>, और इसलिए, c और <math>\log_b a</math> बराबर हैं | :<math>\log_b a = \log_2 2 = 1</math>, और इसलिए, c और <math>\log_b a</math> बराबर हैं | ||
तो यह मास्टर प्रमेय के दूसरे | तो यह मास्टर प्रमेय के दूसरे स्थिति से आता है: | ||
:<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math> इस प्रकार दिया गया पुनरावृत्ति संबंध <math>T(n)</math> में <math>\Theta(n \log n)</math> था. | :<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math> इस प्रकार दिया गया पुनरावृत्ति संबंध <math>T(n)</math> में <math>\Theta(n \log n)</math> था. | ||
Line 186: | Line 186: | ||
:<math> 2 \left(\frac{n^2}{4}\right) \le k n^2 </math>, चुनना <math> k = 1/2 </math> | :<math> 2 \left(\frac{n^2}{4}\right) \le k n^2 </math>, चुनना <math> k = 1/2 </math> | ||
तो यह मास्टर प्रमेय के तीसरे | तो यह मास्टर प्रमेय के तीसरे स्थिति से आता है: | ||
:<math>T \left(n \right) = \Theta\left(f(n)\right) = \Theta \left(n^2 \right).</math> | :<math>T \left(n \right) = \Theta\left(f(n)\right) = \Theta \left(n^2 \right).</math> | ||
Line 194: | Line 194: | ||
== अस्वीकार्य समीकरण == | == अस्वीकार्य समीकरण == | ||
मास्टर प्रमेय का उपयोग करके निम्नलिखित समीकरणों को | मास्टर प्रमेय का उपयोग करके निम्नलिखित समीकरणों को समाधान नहीं किया जा सकता है:<ref> | ||
Massachusetts Institute of Technology (MIT), | Massachusetts Institute of Technology (MIT), | ||
"Master Theorem: Practice Problems and Solutions", | "Master Theorem: Practice Problems and Solutions", | ||
Line 202: | Line 202: | ||
*: a स्थिरांक नहीं है; उप-समस्याओं की संख्या निश्चित की जानी चाहिए | *: a स्थिरांक नहीं है; उप-समस्याओं की संख्या निश्चित की जानी चाहिए | ||
*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> | *<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> | ||
*: के बीच गैर-बहुपद अंतर <math>f(n)</math> और <math>n^{\log_b a}</math> (नीचे देखें; विस्तारित संस्करण | *: के बीच गैर-बहुपद अंतर <math>f(n)</math> और <math>n^{\log_b a}</math> (नीचे देखें; विस्तारित संस्करण प्रायुक्त होता है) | ||
*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> | *<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> | ||
*:<math> a<1 </math> एक से कम उप समस्या नहीं हो सकती | *:<math> a<1 </math> एक से कम उप समस्या नहीं हो सकती | ||
Line 210: | Line 210: | ||
*:स्थिति 3 लेकिन नियमितता का उल्लंघन। | *:स्थिति 3 लेकिन नियमितता का उल्लंघन। | ||
उपरोक्त दूसरे अस्वीकार्य उदाहरण में, के बीच का अंतर <math>f(n)</math> और <math>n^{\log_b a}</math> अनुपात में व्यक्त किया जा सकता है <math>\frac{f(n)}{n^{\log_b a}} = \frac{n / \log n}{n^{\log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n}</math>. यह स्पष्ट है कि <math>\frac{1}{\log n} < n^\epsilon</math> किसी स्थिरांक के लिए <math>\epsilon > 0</math>. इसलिए, अंतर बहुपद नहीं है और मास्टर प्रमेय का मूल रूप | उपरोक्त दूसरे अस्वीकार्य उदाहरण में, के बीच का अंतर <math>f(n)</math> और <math>n^{\log_b a}</math> अनुपात में व्यक्त किया जा सकता है <math>\frac{f(n)}{n^{\log_b a}} = \frac{n / \log n}{n^{\log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n}</math>. यह स्पष्ट है कि <math>\frac{1}{\log n} < n^\epsilon</math> किसी स्थिरांक के लिए <math>\epsilon > 0</math>. इसलिए, अंतर बहुपद नहीं है और मास्टर प्रमेय का मूल रूप प्रायुक्त नहीं होता है। विस्तारित रूप (स्थिति 2बी) समाधान <math>T(n) = \Theta(n\log\log n)</math> देते हुए प्रायुक्त होता है. | ||
== सामान्य एल्गोरिदम के लिए आवेदन == | == सामान्य एल्गोरिदम के लिए आवेदन == | ||
Line 223: | Line 223: | ||
| <math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math> | | <math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math> | ||
| <math>O(\log n)</math> | | <math>O(\log n)</math> | ||
| मास्टर प्रमेय <math>c = \log_b a</math> | | मास्टर प्रमेय <math>c = \log_b a</math> स्थिति प्रायुक्त करें, जहाँ <math>a = 1, b = 2, c = 0, k = 0</math><ref name="dartmouth"> | ||
Dartmouth College, | Dartmouth College, | ||
http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf | http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf | ||
Line 231: | Line 231: | ||
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math> | | <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math> | ||
| <math>O(n)</math> | | <math>O(n)</math> | ||
| मास्टर प्रमेय <math>c < \log_b a</math> | | मास्टर प्रमेय <math>c < \log_b a</math> स्थिति प्रायुक्त करें जहाँ <math>a = 2, b = 2, c = 0</math><ref name="dartmouth" /> | ||
|- | |- | ||
| इष्टतम क्रमबद्ध मैट्रिक्स खोज | | इष्टतम क्रमबद्ध मैट्रिक्स खोज | ||
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)</math> | | <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)</math> | ||
| <math>O(n)</math> | | <math>O(n)</math> | ||
| <math>p=1</math> and <math>g(u)=\log(u)</math> से पाने के <math>\Theta(2n - \log n)</math> के लिए [[Akra–Bazzi theorem|एकरा-बाज़ी प्रमेय]] | | <math>p=1</math> and <math>g(u)=\log(u)</math> से पाने के <math>\Theta(2n - \log n)</math> के लिए [[Akra–Bazzi theorem|एकरा-बाज़ी प्रमेय]] प्रायुक्त करें | ||
|- | |- | ||
| [[Merge sort|मर्ज़ सॉर्ट]] | | [[Merge sort|मर्ज़ सॉर्ट]] | ||
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math> | | <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math> | ||
| <math>O(n \log n)</math> | | <math>O(n \log n)</math> | ||
| मास्टर प्रमेय case <math>c = \log_b a</math> | | मास्टर प्रमेय case <math>c = \log_b a</math> स्थिति प्रायुक्त करे, जहाँ <math>a = 2, b = 2, c = 1, k = 0</math> | ||
|} | |} | ||
Revision as of 06:02, 15 February 2023
एल्गोरिदम के विश्लेषण में, विभाजन और जीत पुनरावृत्ति के लिए मास्टर प्रमेय कई विभाजन और जीत एल्गोरिदम के विश्लेषण में होने वाले प्रकार के पुनरावृत्ति संबंधों के लिए स्पर्शोन्मुख विश्लेषण (बिग ओ नोटेशन का उपयोग करके) प्रदान करता है। यह दृष्टिकोण पहली बार 1980 में जॉन बेंटले (कंप्यूटर वैज्ञानिक), डोरोथिया ब्लोस्टीन (नी हेकेन) और जेम्स बी सक्से द्वारा प्रस्तुत किया गया था, जहां इसे इस प्रकार की पुनरावृत्ति का समाधान करने के लिए एकीकृत विधि के रूप में वर्णित किया गया था।[1] मास्टर प्रमेय का नाम व्यापक रूप से उपयोग किए जाने वाले एल्गोरिदम पाठ्यपुस्तक एल्गोरिदम का परिचय (एल्गोरिदम टेक्स्टबुक इंट्रोडक्शन टू एल्गोरिदम) द्वारा थॉमस एच. कॉर्मेन, चार्ल्स ई. लीसरसन, रॉन रिवेस्ट और क्लिफर्ड स्टीन द्वारा लोकप्रिय किया गया था।
इस प्रमेय के उपयोग से सभी पुनरावृत्ति संबंधों को समाधान नहीं किया जा सकता है; इसके सामान्यीकरण में अकरा-बाज़ी पद्धति सम्मिलित है।
परिचय
समस्या पर विचार करें जिसे पुनरावर्ती एल्गोरिथम का उपयोग करके समाधान किया जा सकता है जैसे कि निम्नलिखित:
procedure p(input x of size n):
if n < some constant k:
Solve x directly without recursion
else:
Create a subproblems of x, each having size n/b
Call procedure p recursively on each subproblem
Combine the results from the subproblems
उपरोक्त कलन विधि समस्या को पुनरावर्ती रूप से कई उप-समस्याओं में विभाजित करता है, प्रत्येक उप-समस्या आकार n/b की होती है. इसके समाधान के पेड़ में प्रत्येक पुनरावर्ती कॉल के लिए एक नोड होता है, उस नोड के बच्चे उस कॉल से किए गए अन्य कॉल होते हैं। पेड़ की पत्तियां पुनरावर्तन के आधार स्थिति हैं, उप-समस्याएं (के से कम आकार की) जो पुनरावर्तन नहीं करती हैं। उपरोक्त उदाहरण a प्रत्येक गैर-पत्ती नोड पर चाइल्ड नोड होगा। प्रत्येक नोड काम की मात्रा करता है जो उप-समस्या n के आकार के अनुरूप होता है। पुनरावर्ती कॉल के उस उदाहरण को पास किया गया और इसके द्वारा दिया गया . संपूर्ण एल्गोरिथम द्वारा किए गए कार्य की कुल राशि ट्री में सभी नोड्स द्वारा किए गए कार्य का योग है।
एल्गोरिथम का रनटाइम जैसे आकार 'n' के इनपुट पर ऊपर 'p', सामान्यतः द्वारा निरूपित किया जाता है, पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है
जहाँ उपरोक्त प्रक्रिया में उप-समस्याओं को बनाने और उनके परिणामों को संयोजित करने का समय है। किए गए कार्य की कुल राशि के लिए व्यंजक प्राप्त करने के लिए इस समीकरण को क्रमिक रूप से स्वयं में प्रतिस्थापित किया जा सकता है और विस्तारित किया जा सकता है।[2] मास्टर प्रमेय इस रूप के कई पुनरावृत्ति संबंधों को पुनरावर्ती संबंध का विस्तार किए बिना सीधे बिग Θ-संकेतन में परिवर्तित करने की अनुमति देता है।
सामान्य रूप
मास्टर प्रमेय हमेशा विभाजित और जीत एल्गोरिदम से पुनरावृत्ति के लिए असम्बद्ध रूप से तंग सीमा उत्पन्न करता है जो इनपुट को समान आकार के छोटे उप-समस्याओं में विभाजित करता है, उप-समस्याओं को पुनरावर्ती रूप से समाधान करता है, और फिर मूल समस्या का समाधान देने के लिए उप-समस्या समाधानों को जोड़ता है। इस प्रकार के कलन विधि के लिए समय उस कार्य को जोड़कर व्यक्त किया जा सकता है जो वे अपने पुनरावर्तन के शीर्ष स्तर पर (समस्याओं को उप-समस्याओं में विभाजित करने के लिए और फिर उप-समस्याओं के समाधानों को संयोजित करने के लिए) एक साथ कलन विधि के पुनरावर्ती कॉल में किए गए समय के साथ करते हैं। यदि आकार के इनपुट पर कलन विधि के लिए कुल समय को दर्शाता है, और पुनरावृत्ति के शीर्ष स्तर पर लगने वाले समय की मात्रा को दर्शाता है तो समय को पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है जो रूप लेता है:
यहाँ एक इनपुट समस्या का आकार है, पुनरावर्तन में उपसमस्याओं की संख्या है, और वह कारक है जिसके द्वारा प्रत्येक पुनरावर्ती कॉल (b> 1) में उप-समस्या का आकार कम हो जाता है। महत्वपूर्ण रूप से, और पर निर्भर नहीं होना चाहिए. नीचे दिया गया प्रमेय यह भी मानता है कि, पुनरावृत्ति के आधार स्थिति के रूप में, तब किसी सीमा से कम है, सबसे छोटा इनपुट आकार जो पुनरावर्ती कॉल की ओर ले जाएगा।
समस्या को विभाजित/पुन: संयोजित करने के कार्य के आधार पर, इस फ़ॉर्म की पुनरावृत्ति अधिकांश निम्नलिखित तीन शासनों में से एक को संतुष्ट करती है महत्वपूर्ण घातांक . (नीचे दी गई तालिका मानक बिग ओ नोटेशन का उपयोग करती है) से संबंधित है।
स्थिति | विवरण | के संबंध में, अर्थात्, पर स्थिति | मास्टर प्रमेय बाध्य | सांकेतिक उदाहरण |
---|---|---|---|---|
1 | किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं से बौना हो जाता है।
अर्थात् पुनरावर्तन वृक्ष पत्ती-भारी है |
जब जहाँ
(कम एक्सपोनेंट बहुपद द्वारा ऊपरी-सीमित) |
... तब
(विभाजन शब्द प्रकट नहीं होता है; पुनरावर्ती वृक्ष संरचना हावी है।) |
यदि and , तब . |
2 | किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं के बराबर है। | जब के लिये a
(महत्वपूर्ण-प्रतिपादक बहुपद द्वारा सीमाबद्ध, शून्य या अधिक वैकल्पिक s) |
... तब
(बाध्य बंटवारे की अवधि है, जहां लॉग को एक शक्ति द्वारा संवर्धित किया जाता है।) |
यदि and , फिर .
यदि और , तब . |
3 | किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं पर हावी हो जाता है।
अर्थात् रिकर्सन ट्री रूट-हैवी है। |
जब जहाँ
(अधिक-प्रतिपादक बहुपद द्वारा निम्न-परिबद्ध) |
... यह आवश्यक रूप से कुछ भी नहीं देता है। इसके अतिरिक्त, यदि
तो कुल बंटवारे की अवधि का प्रभुत्व है : |
यदि और और फिर नियमितता की स्थिति बनी रहती है. |
स्थिति 2 का एक उपयोगी विस्तार सभी मानो को संभालता है:[3]
स्थिति | के संबंध में, अर्थात्, पर स्थिति | मास्टर प्रमेय बाध्य | सांकेतिक उदाहरण |
---|---|---|---|
2a | जब कोई के लिये | ...तब
(बाध्य बंटवारे की अवधि है, जहां लॉग को एक शक्ति द्वारा संवर्धित किया जाता है।) |
यदि और , तब . |
2b | जब के लिये | ... जब
(बाध्य बंटवारे की अवधि है, जहां लॉग व्युत्क्रम को पुनरावृत्त log द्वारा प्रतिस्थापित किया जाता है।) |
यदि और , तब . |
2c | जब कोई के लिये | ... जब
(बाध्य बंटवारे की अवधि है, जहां log गायब हो जाता है।) |
यदि और , तब . |
उदाहरण
पहला उदाहरण
जैसा कि उपरोक्त सूत्र से देखा जा सकता है:
- , इसलिए
- , जहाँ
अगला, हम देखते हैं कि क्या हम स्थिति 1 शर्त को पूरा करते हैं:
- .
यह मास्टर प्रमेय के पहले स्थिति से अनुसरण करता है
(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो , मानते हुए ) है.
स्थिति 2 उदाहरण
जैसा कि हम उपरोक्त सूत्र में देख सकते हैं कि चरों को निम्नलिखित मान मिलते हैं:
- जहाँ
अगला, हम देखते हैं कि क्या हम स्थिति 2 शर्त को पूरा करते हैं:
- , और इसलिए, c और बराबर हैं
तो यह मास्टर प्रमेय के दूसरे स्थिति से आता है:
- इस प्रकार दिया गया पुनरावृत्ति संबंध में था.
(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो , मानते हुए ) है.
स्थिति 3 उदाहरण
जैसा कि हम उपरोक्त सूत्र में देख सकते हैं कि चरों को निम्नलिखित मान मिलते हैं:
- , जहाँ
अगला, हम देखते हैं कि क्या हम स्थिति 3 शर्त को पूरा करते हैं:
- , और इसलिए, हाँ,
नियमितता की स्थिति भी रखती है:
- , चुनना
तो यह मास्टर प्रमेय के तीसरे स्थिति से आता है:
इस प्रकार दिया गया पुनरावृत्ति संबंध में था , जो इसका मूल सूत्र का अनुपालन करता है।
(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो , मानते हुए .) है.
अस्वीकार्य समीकरण
मास्टर प्रमेय का उपयोग करके निम्नलिखित समीकरणों को समाधान नहीं किया जा सकता है:[4]
-
- a स्थिरांक नहीं है; उप-समस्याओं की संख्या निश्चित की जानी चाहिए
-
- के बीच गैर-बहुपद अंतर और (नीचे देखें; विस्तारित संस्करण प्रायुक्त होता है)
-
- एक से कम उप समस्या नहीं हो सकती
-
- , जो संयोजन समय सकारात्मक नहीं है
-
- स्थिति 3 लेकिन नियमितता का उल्लंघन।
उपरोक्त दूसरे अस्वीकार्य उदाहरण में, के बीच का अंतर और अनुपात में व्यक्त किया जा सकता है . यह स्पष्ट है कि किसी स्थिरांक के लिए . इसलिए, अंतर बहुपद नहीं है और मास्टर प्रमेय का मूल रूप प्रायुक्त नहीं होता है। विस्तारित रूप (स्थिति 2बी) समाधान देते हुए प्रायुक्त होता है.
सामान्य एल्गोरिदम के लिए आवेदन
कलन विधि | पुनरावर्ती संबंध | कार्यावधि | टिप्पणी |
---|---|---|---|
बाइनरी खोज | मास्टर प्रमेय स्थिति प्रायुक्त करें, जहाँ [5] | ||
बाइनरी ट्री ट्रैवर्सल | मास्टर प्रमेय स्थिति प्रायुक्त करें जहाँ [5] | ||
इष्टतम क्रमबद्ध मैट्रिक्स खोज | and से पाने के के लिए एकरा-बाज़ी प्रमेय प्रायुक्त करें | ||
मर्ज़ सॉर्ट | मास्टर प्रमेय case स्थिति प्रायुक्त करे, जहाँ |
यह भी देखें
- एकरा–बाजी विधि
- स्पर्शोन्मुख जटिलता
टिप्पणियाँ
- ↑ Bentley, Jon Louis; Haken, Dorothea; Saxe, James B. (September 1980), "A general method for solving divide-and-conquer recurrences", ACM SIGACT News, 12 (3): 36–44, doi:10.1145/1008861.1008865, S2CID 40642274, archived from the original on September 22, 2017
- ↑ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
- ↑ Chee Yap, A real elementary approach to the master recurrence and generalizations, Proceedings of the 8th annual conference on Theory and applications of models of computation (TAMC'11), pages 14–26, 2011. Online copy.
- ↑ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", https://people.csail.mit.edu/thies/6.046-web/master.pdf
- ↑ 5.0 5.1 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf
संदर्भ
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.
- Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.