मेडियन के औसत

Question

मैंने रैखिक समय ओ (एन) में आकार एन की सरणी में के-वें सबसे छोटे (या सबसे बड़े) तत्व को खोजने के लिए ऑर्डर आंकड़े पढ़े हैं।

एक कदम है कि इसे मध्यस्थों के औसत को खोजने की आवश्यकता है।

1. सरणी को [n/5] भागों में विभाजित करें। प्रत्येक भाग में 5 तत्व होते हैं।
2. प्रत्येक भाग में औसत खोजें। (हमारे पास [n/5] संख्याएं हैं)
3. चरण 1 और 2 दोहराएं जब तक कि हमारे पास केवल अंतिम संख्या न हो। (अर्थात पुनरावर्ती)

टी (एन) = टी (एन/5) + O (एन) और हम टी (एन) प्राप्त कर सकते हैं = हे (एन)।

लेकिन, क्या यह सच है कि, आखिरकार जो संख्या हम प्राप्त करते हैं वह मध्यस्थों का औसत नहीं है, लेकिन मध्यस्थों के मध्यस्थों के मध्यस्थों के मध्यस्थों का औसत, यदि हमारे पास एक बड़ी सरणी है।

कृपया एक सरणी पर विचार करें जिसमें 125 तत्व हैं।

सबसे पहले, यह 25 भागों में विभाजित है और हमें 25 औसत मिलते हैं। फिर, हम इन 25 संख्याओं को 5 भागों में विभाजित करते हैं और 5 medians, पाते हैं अंत में, हम उस संख्या को प्राप्त करते हैं जो मध्यस्थों के मध्यस्थों का औसत है। (मध्यस्थों का औसत नहीं)

मुझे इसकी परवाह करने का कारण यह है कि, मैं समझ सकता हूं कि [3/4] * एन तत्वों में से अधिकांश हैं जो मध्यस्थों के मध्य से छोटे (या बड़े) हैं। लेकिन क्या होगा यदि यह मध्यस्थों का औसत नहीं है लेकिन मध्यस्थों के मध्यस्थों का औसत है? बदतर मामले में पिटोट की तुलना में छोटे तत्व (या बड़े) होने वाले कम तत्व होने चाहिए, जिसका अर्थ है कि पिवट सरणी की सीमा के करीब है।

यदि हमारे पास बहुत बड़ी सरणी है, और हमने मध्यस्थों के मध्यस्थों के मध्यस्थों के मध्यस्थों के मध्यस्थों का औसत पाया। सबसे बुरे मामले में हमने जो पिवट पाया वह अभी भी बाध्य के बहुत करीब हो सकता है और इस मामले में समय जटिलता क्या है?

मैंने 125 तत्वों का एक डेटासेट बनाया है। परिणाम 9 है?

0.8 0.9 1 inf inf 
1.8 1.9 2 inf inf 
6.8 6.9 7 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

2.8 2.9 3 inf inf 
3.8 3.9 4 inf inf 
7.8 7.9 8 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

4.8 4.9 5 inf inf 
5.8 5.9 6 inf inf 
8.8 8.9 9 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

जहां inf का मतलब है कि संख्या काफी बड़ी है।

Answer 1

आइए मध्यस्थों के मध्यस्थों के अपने औसत को इंगित करें ... [median of] * = एम।

सबसे पहले, मेरा मानना ​​है कि मध्यस्थों के औसत एल्गोरिदम (एक अच्छा पिवट चुनने के लिए) रिकर्सिव नहीं है। एल्गोरिथ्म इस प्रकार है:

1. स्प्लिट 5
2. के समूह में तत्वों प्रत्येक समूह
3. की औसत खोजें माध्यिकाओं की औसत का पता लगाएं और एक धुरी के रूप में उपयोग करें।

मध्यस्थों का औसत 3 एन/10 तत्वों से छोटा होगा और 3 एन/10 तत्वों से बड़ा होगा, न कि 3 एन/4। मध्यस्थों का चयन करने के बाद आपके पास एन/5 संख्याएं हैं। मध्यस्थ का औसत उन संख्याओं के आधे से अधिक/छोटा है, जो एन/10 है। उनमें से प्रत्येक संख्या एक औसत है, इसलिए यह 2 संख्याओं से अधिक/छोटा है, जिससे आप एक और 2 एन/10 नंबर दे सकते हैं। अब कुल मिलाकर, आपको एन/10 + 2 एन/10 = 3 एन/10 नंबर मिलते हैं।

1, 2, 7, inf, inf 
3, 4, 8, inf, inf 
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf. 

तो माध्यिकाओं की औसत वास्तव में 9.

होगा:

अपने उदाहरण डेटासेट में 5 के समूह इकट्ठा करने और उनके माध्यिकाओं की गणना के बाद अपने दूसरे प्रश्न को हल करने के लिए, हम निम्न क्रम होगा

आपका प्रस्तावित [की औसत] * एल्गोरिथ्म के क्रम हो जाएगा:

T(n) = O(n * log(n)) 

अब चलो का विश्लेषण करने के कितने संख्या हम कम है की कोशिश करते हैं/से अधिक एम।

• गहराई 1: हम निम्नलिखित समूह हैं n/5 तत्वों सभी माध्यिकाओं
• गहराई 2: n/25 तत्वों सभी माध्यिकाओं
• ...
• गहराई मैं: n/(5^i) तत्वों सभी माध्यिकाओं

प्रत्येक समूह में कम है/पिछले गहराई है, जो पिछले गहराई के कम/अधिक से अधिक 2 तत्वों, और इतने पर है की अधिक से अधिक से अधिक 2 तत्वों:

+०१२३५१६४१०६१

कुल मिलाकर, हम पाते हैं कि हमारे एम (एन * (2^के) + के * एन)/((2^के) * (5^के)) से अधिक/कम है। गहराई = 1 के लिए आपको मध्यस्थों का औसत मिलता है, जो 3 एन/10 है।

अब आप अपने गहराई संभालने [log_5 (एन)], यानी एन = 5^कश्मीर है, हम पाते हैं:

5^कश्मीर * (k + 2^ट)/(5^कश्मीर * 2^कश्मीर) जो है -> 1.