मास्टर प्रमेय (एल्गोरिदम का विश्लेषण): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 27: Line 27:
== सामान्य रूप ==
== सामान्य रूप ==


मास्टर प्रमेय हमेशा विभाजित और जीत एल्गोरिदम से पुनरावृत्ति के लिए असम्बद्ध रूप से तंग सीमा उत्पन्न करता है जो इनपुट को समान आकार के छोटे उप-समस्याओं में विभाजित करता है, उप-समस्याओं को पुनरावर्ती रूप से हल करता है, और फिर मूल समस्या का समाधान देने के लिए उप-समस्या समाधानों को जोड़ता है। इस तरह के एल्गोरिथ्म के लिए समय उस कार्य को जोड़कर व्यक्त किया जा सकता है जो वे अपने पुनरावर्तन के शीर्ष स्तर पर करते हैं (समस्याओं को उप-समस्याओं में विभाजित करने के लिए और फिर उप-समस्याओं के समाधानों को संयोजित करने के लिए) एक साथ एल्गोरिथ्म के पुनरावर्ती कॉल में किए गए समय के साथ। अगर <math>T(n)</math> आकार के इनपुट पर एल्गोरिथ्म के लिए कुल समय को दर्शाता है <math>n</math>, और <math>f(n)</math> पुनरावृत्ति के शीर्ष स्तर पर लगने वाले समय की मात्रा को दर्शाता है तो समय को पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है जो रूप लेता है:
मास्टर प्रमेय हमेशा विभाजित और जीत एल्गोरिदम से पुनरावृत्ति के लिए असम्बद्ध रूप से तंग सीमा उत्पन्न करता है जो इनपुट को समान आकार के छोटे उप-समस्याओं में विभाजित करता है, उप-समस्याओं को पुनरावर्ती रूप से हल करता है, और फिर मूल समस्या का समाधान देने के लिए उप-समस्या समाधानों को जोड़ता है। इस तरह के एल्गोरिथ्म के लिए समय उस कार्य को जोड़कर व्यक्त किया जा सकता है जो वे अपने पुनरावर्तन के शीर्ष स्तर पर (समस्याओं को उप-समस्याओं में विभाजित करने के लिए और फिर उप-समस्याओं के समाधानों को संयोजित करने के लिए) एक साथ एल्गोरिथ्म के पुनरावर्ती कॉल में किए गए समय के साथ करते हैं। अगर <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> वह कारक है जिसके द्वारा प्रत्येक पुनरावर्ती कॉल (बी> 1) में उप-समस्या का आकार कम हो जाता है। महत्वपूर्ण रूप से, <math>a</math> और <math>b</math> पर निर्भर नहीं होना चाहिए <math>n</math>. नीचे दिया गया प्रमेय यह भी मानता है कि, पुनरावृत्ति के आधार मामले के रूप में, <math>T(n)=\Theta(1)</math> कब <math>n</math> किसी सीमा से कम है <math>\kappa > 0</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>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 37: Line 37:
{| class="wikitable"
{| class="wikitable"
|-
|-
! width=10|Case
! width=10|स्थिति
! Description
! विवरण
! Condition on <math>f(n)</math> in relation to <math>c_{\operatorname{crit}}</math>, i.e. <math>\log_b a</math>
! <math>f(n)</math> <math>c_{\operatorname{crit}}</math> के संबंध में, यानी, <math>\log_b a</math> पर स्थिति
! Master Theorem bound
! मास्टर प्रमेय बाध्य
! width=400|Notational examples
! width=400|सांकेतिक उदाहरण
|-
|-




! 1
! 1
| Work to split/recombine a problem is dwarfed by subproblems.
| किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं से बौना हो जाता है।
यानी पुनरावर्तन वृक्ष पत्ती-भारी है
| जब <math>f(n) = O(n^{c})</math> जहाँ <math>c<c_{\operatorname{crit}}</math>


i.e. the recursion tree is leaf-heavy
(कम एक्सपोनेंट बहुपद द्वारा ऊपरी-सीमित)
| When <math>f(n) = O(n^{c})</math> where <math>c<c_{\operatorname{crit}}</math>


(upper-bounded by a lesser exponent polynomial)
| ... तब <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>


| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>
(विभाजन शब्द प्रकट नहीं होता है; पुनरावर्ती वृक्ष संरचना हावी है।)


(The splitting term does not appear; the recursive tree structure dominates.)
| यदि <math>b=a^2</math> and <math>f(n) = O(n^{1/2-\epsilon})</math>, तब <math>T(n) = \Theta(n^{1/2})</math>.
 
| If <math>b=a^2</math> and <math>f(n) = O(n^{1/2-\epsilon})</math>, then <math>T(n) = \Theta(n^{1/2})</math>.


|-
|-
Line 63: Line 62:


! 2
! 2
| Work to split/recombine a problem is comparable to subproblems.
| किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं के बराबर है।
| When <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> for a <math>k \ge 0</math>
| जब<math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> के लिये a <math>k \ge 0</math>


(rangebound by the critical-exponent polynomial, times zero or more optional <math>\log</math>s)
(महत्वपूर्ण-प्रतिपादक बहुपद द्वारा सीमाबद्ध, शून्य या अधिक वैकल्पिक <math>\log</math>s)


| ... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)</math>
| ... तब <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)</math>


(The bound is the splitting term, where the log is augmented by a single power.)
(बाध्य बंटवारे की अवधि है, जहां लॉग को एक शक्ति द्वारा संवर्धित किया जाता है।)


| If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2})</math>, then <math>T(n) = \Theta(n^{1/2} \log n)</math>.
| यदि <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2})</math>, फिर <math>T(n) = \Theta(n^{1/2} \log n)</math>.


If <math>b=a^2</math> and <math>f(n) = \Theta(n^{1/2} \log n)</math>, then <math>T(n) = \Theta(n^{1/2} \log^{2} n)</math>.
यदि <math>b=a^2</math> और <math>f(n) = \Theta(n^{1/2} \log n)</math>, तब <math>T(n) = \Theta(n^{1/2} \log^{2} n)</math>.


|-
|-
Line 80: Line 79:


! 3
! 3
| Work to split/recombine a problem dominates subproblems.
| किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं पर हावी हो जाता है।
 
यानी रिकर्सन ट्री रूट-हैवी है।
i.e. the recursion tree is root-heavy.
| जब <math>f(n) = \Omega(n^{c})</math> जहाँ <math>c>c_{\operatorname{crit}}</math>  
| When <math>f(n) = \Omega(n^{c})</math> where <math>c>c_{\operatorname{crit}}</math>  


(lower-bounded by a greater-exponent polynomial)
(अधिक-प्रतिपादक बहुपद द्वारा निम्न-परिबद्ध)


| ... this doesn't necessarily yield anything. Furthermore, if
| ... यह आवश्यक रूप से कुछ भी नहीं देता है। इसके अलावा, अगर


:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for some constant <math>k < 1</math> and sufficiently large <math>n</math> (often called the ''regularity condition'')
:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for कुछ स्थिर <math>k < 1</math> और और काफी बड़ा <math>n</math> (अक्सर नियमितता की स्थिति कहा जाता है)


then the total is dominated by the splitting term <math>f(n)</math>:
तो कुल बंटवारे की अवधि का प्रभुत्व है <math>f(n)</math>:


:<math>T\left(n \right) = \Theta\left(f(n) \right)</math>
:<math>T\left(n \right) = \Theta\left(f(n) \right)</math>


| If <math>b=a^2</math> and <math>f(n) = \Omega(n^{1/2+\epsilon})</math> and the regularity condition holds, then <math>T(n) = \Theta(f(n))</math>.
| यदि <math>b=a^2</math> और <math>f(n) = \Omega(n^{1/2+\epsilon})</math> और फिर नियमितता की स्थिति <math>T(n) = \Theta(f(n))</math> बनी रहती है.


|}
|}
Line 104: Line 102:
{| class="wikitable"
{| class="wikitable"
|-
|-
! width=10|Case
! width=10|स्थिति
! Condition on <math>f(n)</math> in relation to <math>c_{\operatorname{crit}}</math>, i.e. <math>\log_b a</math>
! <math>f(n)</math> <math>c_{\operatorname{crit}}</math> के संबंध में, यानी,  <math>\log_b a</math> पर स्थिति
! Master Theorem bound
! मास्टर प्रमेय बाध्य
! width=400|Notational examples
! width=400|सांकेतिक उदाहरण


|-
|-

Revision as of 05:28, 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 किसी समस्या को विभाजित/पुन: संयोजित करने का कार्य उप-समस्याओं पर हावी हो जाता है।

यानी रिकर्सन ट्री रूट-हैवी है।

जब जहाँ

(अधिक-प्रतिपादक बहुपद द्वारा निम्न-परिबद्ध)

... यह आवश्यक रूप से कुछ भी नहीं देता है। इसके अलावा, अगर
for कुछ स्थिर और और काफी बड़ा (अक्सर नियमितता की स्थिति कहा जाता है)

तो कुल बंटवारे की अवधि का प्रभुत्व है :

यदि और और फिर नियमितता की स्थिति बनी रहती है.

केस 2 का एक उपयोगी विस्तार सभी मूल्यों को संभालता है :[3]

स्थिति के संबंध में, यानी, पर स्थिति मास्टर प्रमेय बाध्य सांकेतिक उदाहरण
2a When for any ... then

(The bound is the splitting term, where the log is augmented by a single power.)

If and , then .
2b When for ... then

(The bound is the splitting term, where the log reciprocal is replaced by an iterated log.)

If and , then .
2c When for any ... then

(The bound is the splitting term, where the log disappears.)

If and , then .


उदाहरण

पहला उदाहरण

जैसा कि उपरोक्त सूत्र से देखा जा सकता है:

, इसलिए
, जहाँ

अगला, हम देखते हैं कि क्या हम केस 1 शर्त को पूरा करते हैं:

.

यह मास्टर प्रमेय के पहले मामले से अनुसरण करता है

(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो है , मानते हुए ).

केस 2 उदाहरण

जैसा कि हम उपरोक्त सूत्र में देख सकते हैं कि चरों को निम्नलिखित मान मिलते हैं:

जहाँ

अगला, हम देखते हैं कि क्या हम केस 2 शर्त को पूरा करते हैं:

, और इसलिए, सी और बराबर हैं

तो यह मास्टर प्रमेय के दूसरे मामले से आता है:

इस प्रकार दिया गया पुनरावृत्ति संबंध में था .

(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो है , मानते हुए ).

केस 3 उदाहरण

जैसा कि हम उपरोक्त सूत्र में देख सकते हैं कि चरों को निम्नलिखित मान मिलते हैं:

, जहाँ

अगला, हम देखते हैं कि क्या हम केस 3 शर्त को पूरा करते हैं:

, और इसलिए, हाँ,

नियमितता की स्थिति भी रखती है:

, चुनना

तो यह मास्टर प्रमेय के तीसरे मामले से आता है:

इस प्रकार दिया गया पुनरावृत्ति संबंध में था , जो इसका अनुपालन करता है मूल सूत्र का।

(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो है , मानते हुए .)

अस्वीकार्य समीकरण

मास्टर प्रमेय का उपयोग करके निम्नलिखित समीकरणों को हल नहीं किया जा सकता है:[4]

  • a स्थिरांक नहीं है; उप-समस्याओं की संख्या निश्चित की जानी चाहिए
  • के बीच गैर-बहुपद अंतर और (नीचे देखें; विस्तारित संस्करण लागू होता है)
  • एक से कम उप समस्या नहीं हो सकती
  • , जो संयोजन समय है, सकारात्मक नहीं है
  • केस 3 लेकिन नियमितता का उल्लंघन।

उपरोक्त दूसरे अस्वीकार्य उदाहरण में, के बीच का अंतर और अनुपात में व्यक्त किया जा सकता है . यह स्पष्ट है कि किसी स्थिरांक के लिए . इसलिए, अंतर बहुपद नहीं है और मास्टर प्रमेय का मूल रूप लागू नहीं होता है। विस्तारित रूप (केस 2बी) समाधान देते हुए लागू होता है .

सामान्य एल्गोरिदम के लिए आवेदन

Algorithm Recurrence relationship Run time Comment
Binary search Apply Master theorem case , where [5]
Binary tree traversal Apply Master theorem case where [5]
Optimal sorted matrix search Apply the Akra–Bazzi theorem for and to get
Merge sort Apply Master theorem case , where


यह भी देखें

टिप्पणियाँ

  1. 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
  2. Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
  3. 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.
  4. Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", https://people.csail.mit.edu/thies/6.046-web/master.pdf
  5. 5.0 5.1 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf


संदर्भ