समझौता "माध्यिकाओं की औसत" एल्गोरिथ्म

Question

मैं एल्गोरिथ्म "माध्यिकाओं की औसत" निम्न उदाहरण पर समझना चाहते हैं:

हम 45 अलग संख्या 5 तत्वों से प्रत्येक के साथ 9 समूह में विभाजित किया है।

48 43 38 33 28 23 18 13 8 

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10 

51 46 41 36 31 26 21 16 53 

52 47 42 37 32 27 22 17 54 

1. पहला कदम हर समूह (इस मामले में वे पहले से ही हल कर रहे हैं) छँटाई है

2. दूसरा कदम रिकर्सिवली, फाई nd "सही" माध्यिकाओं (50 45 40 35 30 25 20 15 10) की औसत यानी सेट हो जाएगा 2 समूहों में विभाजित:

   50 25 
   
   45 20 
   
   40 15 
   
   35 10 
   
   30 
   

   छँटाई इन 2 समूहों

   30 10 
   
   35 15 
   
   40 20 
   
   45 25 
   
   50 
   

माध्यिकाओं 40 और 15 है, इसके अलावा वहाँ 5 तत्वों से कम कर रहे हैं (मामले में संख्या और भी हैं हम मंझला छोड़ लिया) इसलिए दिए गए मान 15 है, लेकिन माध्यिकाओं के "सही" मंझला (50 45 40 35 30 25 20 15 10) 30 है, 15 जो 45 में से 30% से कम हैं जिनका उल्लेख wikipedia

और T(n) <= T(n/5) + T(7n/10) + O(n) विफल रहता है।

विकिपीडिया उदाहरण में वैसे, मैं प्रत्यावर्तन का परिणाम के रूप में 36. हालांकि, सच मंझला है 47.

तो, मुझे लगता है कि कुछ मामलों में यह प्रत्यावर्तन माध्यिकाओं का सच मंझला वापस नहीं कर सकते। मैं समझना चाहता हूं कि मेरी गलती कहां है।

Answer 1

समस्या उस चरण में है जहां आप मध्यस्थों के सही मध्यस्थ को खोजने के लिए कहते हैं।

50 45 40 35 30 25 20 15 10 

इस डेटा सेट का सच मंझला 30 है, 15. नहीं आप पांच के ब्लॉक में समूहों बंटवारे और उन की औसत लेने के द्वारा इस मंझला नहीं मिल रहा है: अपने उदाहरण में, आप इन माध्यिकाओं था औसत, लेकिन इसके बजाय इस छोटे समूह पर चयन एल्गोरिदम को बुलाकर। अपने तर्क में त्रुटि इस समूह का है कि मंझला संभालने है दो ब्लॉकों

50 45 40 35 30 

और

25 20 15 10 

में ऊपर अनुक्रम विभाजित करके पाया जाता है तो प्रत्येक ब्लॉक की औसत पाने के। इसके बजाय, औसत-मध्य-मेडियन एल्गोरिदम अपने आप को पूर्ण डेटा सेट 50 45 40 35 30 25 20 15 10 पर कॉल कर देगा। आंतरिक रूप से, यह समूह को पांच के ब्लॉक में विभाजित करेगा और उन्हें क्रमबद्ध करेगा, लेकिन विभाजन विभाजन के लिए विभाजन बिंदु निर्धारित करने के लिए ऐसा होता है, और यह इस विभाजन चरण में है कि रिकर्सिव कॉल मध्यस्थों का असली औसत पाएगा , जो इस मामले में 30 होगा। यदि आप मूल एल्गोरिदम में विभाजन चरण के रूप में 30 का उपयोग करते हैं, तो आपको वास्तव में आवश्यकतानुसार बहुत अच्छा विभाजन मिलता है।

आशा है कि इससे मदद मिलती है!

Answer 2

मेडियन एल्गोरिदम के औसत के लिए pseudocode है (थोड़ा सा उदाहरण आपके उदाहरण के अनुरूप)। विकिपीडिया में छद्म कोड selectIdx फ़ंक्शन कॉल की आंतरिक कार्यप्रणाली को चित्रित करने में विफल रहता है।

मैंने स्पष्टीकरण के लिए कोड में टिप्पणियां जोड़ दी हैं।

// L is the array on which median of medians needs to be found. 
// k is the expected median position. E.g. first select call might look like: 
// select (array, N/2), where 'array' is an array of numbers of length N 

select(L,k) 
{ 

    if (L has 5 or fewer elements) { 
     sort L 
     return the element in the kth position 
    } 

    partition L into subsets S[i] of five elements each 
     (there will be n/5 subsets total). 

    for (i = 1 to n/5) do 
     x[i] = select(S[i],3) 

    M = select({x[i]}, n/10) 

    // The code to follow ensures that even if M turns out to be the 
    // smallest/largest value in the array, we'll get the kth smallest 
    // element in the array 

    // Partition array into three groups based on their value as 
    // compared to median M 

    partition L into L1<M, L2=M, L3>M 

    // Compare the expected median position k with length of first array L1 
    // Run recursive select over the array L1 if k is less than length 
    // of array L1 
    if (k <= length(L1)) 
     return select(L1,k) 

    // Check if k falls in L3 array. Recurse accordingly 
    else if (k > length(L1)+length(L2)) 
     return select(L3,k-length(L1)-length(L2)) 

    // Simply return M since k falls in L2 
    else return M 

} 

अपने उदाहरण ले रहा है:

माध्यिकाओं समारोह की औसत 45 तत्वों की तरह (k = 45/2 = 22 के साथ) के पूरे सरणी पर बुलाया जाएगा:

median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2) 

1. पहली बार M = select({x[i]}, n/10) कहा जाता है, सर {x[i]} में निम्नलिखित संख्याएं होंगी: 50 45 40 35 30 20 15 10। इस कॉल को n = 45, और इसलिए चुनिंदा समारोह कॉल में हो जाएगा M = select({50 45 40 35 30 20 15 10}, 4)

2. दूसरी बार M = select({x[i]}, n/10) कहा जाता है, सरणी {x[i]} निम्नलिखित संख्या में शामिल होंगे: 40 20। इस कॉल में, n = 9 और इसलिए कॉल M = select({40 20}, 0) होगा। यह चयन कॉल वापस आएगा और मान M = 20 असाइन करेगा।
   
   अब, उस बिंदु पर आ रहा है जहां आपको संदेह था, अब हम M = 20k = 4 के साथ सरणी L विभाजन करते हैं।
   
   याद रखें सरणी L यहां है: 50 45 40 35 30 20 15 10।
   
   सरणी नियम L1 < M, L2 = M और L3 > M के अनुसार L1, L2 और L3 में विभाजित किया जाएगा। इसलिए:
   L1: 10 15
L2: 20
L3: 30 35 40 45 50

k = 4 बाद से, यह length(L1) + length(L2) = 3 से अधिक है। इसलिए, खोज अब निम्नलिखित पुनरावर्ती कॉल के साथ जारी रखा जाएगा:
   return select({30 35 40 45 50}, 1)
   
   जो एक परिणाम के रूप में 30 वापस आ जाएगी:
   return select(L3,k-length(L1)-length(L2))
   
   जो करने के लिए अनुवाद। (चूंकि एल में 5 या कम तत्व हैं, इसलिए यह क्रमशः सरणी में तत्व को वापस कर देगा, जो क्रमबद्ध सरणी में पहली स्थिति है, जो 30 है)।

अब, M = 30 45 तत्वों की पूरी सरणी पर पहले select समारोह कॉल में प्राप्त हो जाएगा, और एक ही विभाजन तर्क जो सरणी L अलग करती है चारों ओर M = 30 अंत में माध्यिकाओं की औसत प्राप्त करने के लिए लागू होगी।

पुhew! मुझे उम्मीद है कि मैं वर्बोज़ था और मेडियन एल्गोरिदम के औसत को समझाने के लिए पर्याप्त स्पष्ट था।