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

For अन्य प्रमेय जिन्हें मास्टर प्रमेय कहा जाता है, see मास्टर प्रमेय.

एल्गोरिदम के विश्लेषण में, विभाजन और जीत पुनरावृत्ति के लिए मास्टर प्रमेय कई विभाजन और जीत एल्गोरिदम के विश्लेषण में होने वाले प्रकार के पुनरावृत्ति संबंधों के लिए स्पर्शोन्मुख विश्लेषण (बिग ओ नोटेशन का उपयोग करके) प्रदान करता है। यह दृष्टिकोण पहली बार 1980 में जॉन बेंटले (कंप्यूटर वैज्ञानिक), डोरोथिया ब्लोस्टीन (नी हेकेन) और जेम्स बी सक्से द्वारा प्रस्तुत किया गया था, जहां इसे इस तरह की पुनरावृत्ति का समाधान करने के लिए एकीकृत विधि के रूप में वर्णित किया गया था। मास्टर प्रमेय का नाम व्यापक रूप से उपयोग किए जाने वाले एल्गोरिदम पाठ्यपुस्तक एल्गोरिदम का परिचय (एल्गोरिदम टेक्स्टबुक इंट्रोडक्शन टू एल्गोरिदम) द्वारा थॉमस एच. कॉर्मेन, चार्ल्स ई. लीसरसन, रॉन रिवेस्ट और क्लिफर्ड स्टीन द्वारा लोकप्रिय किया गया था।

इस प्रमेय के उपयोग से सभी पुनरावृत्ति संबंधों को हल नहीं किया जा सकता है; इसके सामान्यीकरण में अकरा-बाज़ी पद्धति शामिल है।

परिचय

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

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 के आकार के अनुरूप होता है पुनरावर्ती कॉल के उस उदाहरण को पास किया गया और इसके $f(n)$ द्वारा दिया गया . संपूर्ण एल्गोरिथम द्वारा किए गए कार्य की कुल राशि ट्री में सभी नोड्स द्वारा किए गए कार्य का योग है।

एल्गोरिथम का रनटाइम जैसे आकार 'n' के इनपुट पर ऊपर 'p', आमतौर पर $T(n)$ द्वारा निरूपित किया जाता है, पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है

$T(n)=a\;T\left({\frac {n}{b}}\right)+f(n),$

जहाँ $f(n)$ उपरोक्त प्रक्रिया में उप-समस्याओं को बनाने और उनके परिणामों को संयोजित करने का समय है। किए गए कार्य की कुल राशि के लिए व्यंजक प्राप्त करने के लिए इस समीकरण को क्रमिक रूप से स्वयं में प्रतिस्थापित किया जा सकता है और विस्तारित किया जा सकता है। मास्टर प्रमेय इस रूप के कई पुनरावृत्ति संबंधों को पुनरावर्ती संबंध का विस्तार किए बिना सीधे बिग Θ-संकेतन में परिवर्तित करने की अनुमति देता है।

सामान्य रूप

मास्टर प्रमेय हमेशा विभाजित और जीत एल्गोरिदम से पुनरावृत्ति के लिए असम्बद्ध रूप से तंग सीमा उत्पन्न करता है जो इनपुट को समान आकार के छोटे उप-समस्याओं में विभाजित करता है, उप-समस्याओं को पुनरावर्ती रूप से हल करता है, और फिर मूल समस्या का समाधान देने के लिए उप-समस्या समाधानों को जोड़ता है। इस तरह के एल्गोरिथ्म के लिए समय उस कार्य को जोड़कर व्यक्त किया जा सकता है जो वे अपने पुनरावर्तन के शीर्ष स्तर पर करते हैं (समस्याओं को उप-समस्याओं में विभाजित करने के लिए और फिर उप-समस्याओं के समाधानों को संयोजित करने के लिए) एक साथ एल्गोरिथ्म के पुनरावर्ती कॉल में किए गए समय के साथ। अगर $T(n)$ आकार के इनपुट पर एल्गोरिथ्म के लिए कुल समय को दर्शाता है $n$, और $f(n)$ पुनरावृत्ति के शीर्ष स्तर पर लगने वाले समय की मात्रा को दर्शाता है तो समय को पुनरावृत्ति संबंध द्वारा व्यक्त किया जा सकता है जो रूप लेता है:

$T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)$

यहाँ $n$ एक इनपुट समस्या का आकार है, $a$ पुनरावर्तन में उपसमस्याओं की संख्या है, और $b$ वह कारक है जिसके द्वारा प्रत्येक पुनरावर्ती कॉल (बी> 1) में उप-समस्या का आकार कम हो जाता है। महत्वपूर्ण रूप से, $a$ और $b$ पर निर्भर नहीं होना चाहिए $n$. नीचे दिया गया प्रमेय यह भी मानता है कि, पुनरावृत्ति के आधार मामले के रूप में, $T(n)=\Theta (1)$ कब $n$ किसी सीमा से कम है $\kappa >0$, सबसे छोटा इनपुट आकार जो पुनरावर्ती कॉल की ओर ले जाएगा।

समस्या को विभाजित/पुन: संयोजित करने के कार्य के आधार पर, इस फ़ॉर्म की पुनरावृत्ति अक्सर निम्नलिखित तीन शासनों में से एक को संतुष्ट करती है $f(n)$ महत्वपूर्ण प्रतिपादक से संबंधित है $c_{\operatorname {crit} }=\log _{b}a$. (नीचे दी गई तालिका मानक बिग ओ नोटेशन का उपयोग करती है)।

$c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblems}})/\log({\text{relative subproblem size}})$

Case	Description	Condition on $f(n)$ in relation to $c_{\operatorname {crit} }$, i.e. $\log _{b}a$	Master Theorem bound	Notational examples
1	Work to split/recombine a problem is dwarfed by subproblems. i.e. the recursion tree is leaf-heavy	When $f(n)=O(n^{c})$ where $c<c_{\operatorname {crit} }$ (upper-bounded by a lesser exponent polynomial)	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)$ (The splitting term does not appear; the recursive tree structure dominates.)	If $b=a^{2}$ and $f(n)=O(n^{1/2-\epsilon })$, then $T(n)=\Theta (n^{1/2})$.
2	Work to split/recombine a problem is comparable to subproblems.	When $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ for a $k\geq 0$ (rangebound by the critical-exponent polynomial, times zero or more optional $\log$s)	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)$ (The bound is the splitting term, where the log is augmented by a single power.)	If $b=a^{2}$ and $f(n)=\Theta (n^{1/2})$, then $T(n)=\Theta (n^{1/2}\log n)$. If $b=a^{2}$ and $f(n)=\Theta (n^{1/2}\log n)$, then $T(n)=\Theta (n^{1/2}\log ^{2}n)$.
3	Work to split/recombine a problem dominates subproblems. i.e. the recursion tree is root-heavy.	When $f(n)=\Omega (n^{c})$ where $c>c_{\operatorname {crit} }$ (lower-bounded by a greater-exponent polynomial)	... this doesn't necessarily yield anything. Furthermore, if $af\left({\frac {n}{b}}\right)\leq kf(n)$ for some constant $k<1$ and sufficiently large $n$ (often called the regularity condition) then the total is dominated by the splitting term $f(n)$: $T\left(n\right)=\Theta \left(f(n)\right)$	If $b=a^{2}$ and $f(n)=\Omega (n^{1/2+\epsilon })$ and the regularity condition holds, then $T(n)=\Theta (f(n))$.

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

Case	Condition on $f(n)$ in relation to $c_{\operatorname {crit} }$, i.e. $\log _{b}a$	Master Theorem bound	Notational examples
2a	When $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ for any $k>-1$	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)$ (The bound is the splitting term, where the log is augmented by a single power.)	If $b=a^{2}$ and $f(n)=\Theta (n^{1/2}/\log ^{1/2}n)$, then $T(n)=\Theta (n^{1/2}\log ^{1/2}n)$.
2b	When $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ for $k=-1$	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log \log n\right)$ (The bound is the splitting term, where the log reciprocal is replaced by an iterated log.)	If $b=a^{2}$ and $f(n)=\Theta (n^{1/2}/\log n)$, then $T(n)=\Theta (n^{1/2}\log \log n)$.
2c	When $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ for any $k<-1$	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)$ (The bound is the splitting term, where the log disappears.)	If $b=a^{2}$ and $f(n)=\Theta (n^{1/2}/\log ^{2}n)$, then $T(n)=\Theta (n^{1/2})$.

उदाहरण

पहला उदाहरण

$T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}$

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

$a=8,\,b=2,\,f(n)=1000n^{2}$, इसलिए

$f(n)=O\left(n^{c}\right)$, जहाँ $c=2$

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

$\log _{b}a=\log _{2}8=3>c$.

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

$T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)$

(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो है $T(n)=1001n^{3}-1000n^{2}$, मानते हुए $T(1)=1$).

केस 2 उदाहरण

$T(n)=2T\left({\frac {n}{2}}\right)+10n$ जैसा कि हम उपरोक्त सूत्र में देख सकते हैं कि चरों को निम्नलिखित मान मिलते हैं:

$a=2,\,b=2,\,c=1,\,f(n)=10n$

$f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ जहाँ $c=1,k=0$

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

$\log _{b}a=\log _{2}2=1$, और इसलिए, सी और $\log _{b}a$ बराबर हैं

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

$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)$ इस प्रकार दिया गया पुनरावृत्ति संबंध $T(n)$ में था $\Theta (n\log n)$.

(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो है $T(n)=n+10n\log _{2}n$, मानते हुए $T(1)=1$).

केस 3 उदाहरण

$T(n)=2T\left({\frac {n}{2}}\right)+n^{2}$

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

$a=2,\,b=2,\,f(n)=n^{2}$

$f(n)=\Omega \left(n^{c}\right)$, जहाँ $c=2$

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

$\log _{b}a=\log _{2}2=1$, और इसलिए, हाँ, $c>\log _{b}a$

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

$2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}$, चुनना $k=1/2$

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

$T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).$

इस प्रकार दिया गया पुनरावृत्ति संबंध $T(n)$ में था $\Theta (n^{2})$, जो इसका अनुपालन करता है $f(n)$ मूल सूत्र का।

(इस परिणाम की पुष्टि पुनरावृत्ति संबंध के सटीक समाधान से होती है, जो है $T(n)=2n^{2}-n$, मानते हुए $T(1)=1$.)

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

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

• $T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$

  a स्थिरांक नहीं है; उप-समस्याओं की संख्या निश्चित की जानी चाहिए

• $T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$

  के बीच गैर-बहुपद अंतर $f(n)$ और $n^{\log _{b}a}$ (नीचे देखें; विस्तारित संस्करण लागू होता है)

• $T(n)=0.5T\left({\frac {n}{2}}\right)+n$

  $a<1$ एक से कम उप समस्या नहीं हो सकती

• $T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$

  $f(n)$, जो संयोजन समय है, सकारात्मक नहीं है

• $T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$

  केस 3 लेकिन नियमितता का उल्लंघन।

उपरोक्त दूसरे अस्वीकार्य उदाहरण में, के बीच का अंतर $f(n)$ और $n^{\log _{b}a}$ अनुपात में व्यक्त किया जा सकता है ${\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}$. यह स्पष्ट है कि ${\frac {1}{\log n}}<n^{\epsilon }$ किसी स्थिरांक के लिए $\epsilon >0$. इसलिए, अंतर बहुपद नहीं है और मास्टर प्रमेय का मूल रूप लागू नहीं होता है। विस्तारित रूप (केस 2बी) समाधान देते हुए लागू होता है $T(n)=\Theta (n\log \log n)$.

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

Algorithm	Recurrence relationship	Run time	Comment
Binary search	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Apply Master theorem case $c=\log _{b}a$, where $a=1,b=2,c=0,k=0$
Binary tree traversal	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Apply Master theorem case $c<\log _{b}a$ where $a=2,b=2,c=0$
Optimal sorted matrix search	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Apply the Akra–Bazzi theorem for $p=1$ and $g(u)=\log(u)$ to get $\Theta (2n-\log n)$
Merge sort	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Apply Master theorem case $c=\log _{b}a$, where $a=2,b=2,c=1,k=0$

यह भी देखें

• एकरा–बाजी विधि
• स्पर्शोन्मुख जटिलता

संदर्भ

• 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.