विभाजन और विजय एक एल्गोरिदम है जो समस्या को समान प्रकार के कई उप-समस्याओं में पुनरावर्ती रूप से विभाजित करने के प्रतिमान पर काम करता है जिन्हें आसानी से हल किया जा सकता है।
उदाहरण
function recursive(input x size n)
if(n < k)
इनपुट को आकार n/p की m उप-समस्याओं में विभाजित करें
और प्रत्येक उप-समस्या के लिए f को पुनरावर्ती रूप से कॉल करें
else
x को हल करें और लौटाएं
सभी उप-समस्याओं के परिणामों को मिलाएं और मूल समस्या का समाधान लौटाएं
मास्टर प्रमेय पुनरावर्ती संबंध एल्गोरिदम के लिए बड़ा-O मान निर्धारित करने के लिए एक विश्लेषण प्रमेय है। यह एल्गोरिदम द्वारा आवश्यक समय को स्पर्शोन्मुख संकेतन में दर्शाता है।
रनटाइम मान: T(n) = f(n) + m·T(n/p)
कुछ मामलों में मास्टर प्रमेय लागू नहीं होता (जैसे T(n) मोनोटोन नहीं है, या f(n) बहुपद नहीं है)। ऐसे मामलों के लिए उन्नत मास्टर प्रमेय डिज़ाइन किया गया है जो निम्न रूप की पुनरावृत्ति को संभालता है:
T(n) = a·T(n/b) + Θ(nᵏ logᵖ n)
जहां n समस्या का आकार है, a > 0 उप-समस्याओं की संख्या है, b > 1, k ≥ 0, और p एक वास्तविक संख्या है।
हल
- यदि a > bᵏ, तो T(n) = Θ(n^{log_b a})
- यदि a = bᵏ, तो
- यदि p > -1, तो T(n) = Θ(n^{log_b a} log^{p+1} n)
- यदि p = -1, तो T(n) = Θ(n^{log_b a} log log n)
- यदि p < -1, तो T(n) = Θ(n^{log_b a})
- यदि a < bᵏ, तो
- यदि p ≥ 0, तो T(n) = Θ(nᵏ logᵖ n)
- यदि p < 0, तो T(n) = Θ(nᵏ)
उदाहरण
- बाइनरी सर्च: T(n) = Θ(log n)
- मर्ज सॉर्ट: T(n) = Θ(n log n)
