DAA - मैक्स-मिन समस्या

आइए हम एक सरल समस्या पर विचार करें जिसे विभाजित करके और तकनीक को जीतकर हल किया जा सकता है।

समस्या का विवरण

एल्गोरिथ्म विश्लेषण में मैक्स-मिन समस्या एक सरणी में अधिकतम और न्यूनतम मूल्य पा रही है।

समाधान

किसी दिए गए सरणी में अधिकतम और न्यूनतम संख्या खोजने के लिए numbers[] आकार का nनिम्नलिखित एल्गोरिथ्म का उपयोग किया जा सकता है। पहले हम प्रतिनिधित्व कर रहे हैंnaive method और फिर हम प्रस्तुत करेंगे divide and conquer approach।

Nave विधि

Nave विधि किसी भी समस्या को हल करने के लिए एक मूल विधि है। इस विधि में, अधिकतम और न्यूनतम संख्या अलग-अलग पाई जा सकती है। अधिकतम और न्यूनतम संख्या खोजने के लिए, निम्नलिखित सरल एल्गोरिथ्म का उपयोग किया जा सकता है।

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

विश्लेषण

Naive विधि में तुलना की संख्या है 2n - 2।

विभाजन की संख्या को विभाजित और जीत के दृष्टिकोण का उपयोग करके कम किया जा सकता है। निम्नलिखित तकनीक है।

विभाजित और दृष्टिकोण को जीतें

इस दृष्टिकोण में, सरणी को दो हिस्सों में विभाजित किया गया है। फिर पुनरावर्ती दृष्टिकोण का उपयोग करके प्रत्येक पड़ाव में अधिकतम और न्यूनतम संख्याएं पाई जाती हैं। बाद में, प्रत्येक आधे की अधिकतम दो मैक्सिमा और प्रत्येक आधे की न्यूनतम दो मिनीमा लौटाएं।

इस दी गई समस्या में, सरणी में तत्वों की संख्या $ y - x + 1 $ है, जहां y से अधिक या बराबर है x।

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ एक सरणी के अधिकतम और न्यूनतम मान लौटाएगा $ \ mathbf {\ mathit {संख्या [x ... y]}} $।

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

विश्लेषण

चलो T(n) $ \ mathbf {\ mathit {Max - Min (x, y)}} $ द्वारा की गई तुलनाओं की संख्या हो, जहां तत्वों की संख्या $ n = y - x + 1 $ हो।

अगर T(n) संख्याओं का प्रतिनिधित्व करता है, फिर पुनरावृत्ति संबंध के रूप में प्रतिनिधित्व किया जा सकता है

$$ T (n) = \ _ {मामलों} शुरू \ _ \ _ (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} / rceil \ right) ) +2 & for:: n> 2 \\ 1 और for:: = 2 \\ 0 & for \: n = 1 \ अंत {केस} $ $

चलिए हम मान लेते हैं n की शक्ति के रूप में है 2। अत,n = 2^k कहाँ पे k पुनरावृत्ति पेड़ की ऊंचाई है।

इसलिए,

$$ T (n) = 2.T (\ frac {n} {2}) + 2 = 2. \ left (\ start {array} {c} 2.T (\ frac {n} {4}) + 2 \ अंत {सरणी} \ सही) + 2 ..... = \ frac {3n} {2} - 2 $ $

Naquerve विधि की तुलना में, विभाजित और जीत के दृष्टिकोण में, तुलना की संख्या कम है। हालाँकि, दोनों दृष्टिकोणों को स्पर्शोन्मुख संकेतन का उपयोग करके दर्शाया गया हैO(n)।