एन संख्याओं के शीर्ष आधा औसत कैसे खोजें?

Question

एन मनमानी पूर्णांक को देखते हुए, इन संख्याओं के औसत आधे औसत को कैसे प्राप्त करें? क्या कोई ओ (एन) समाधान है? यदि नहीं, तो यह साबित करना संभव है कि यह संभव नहीं है?

Answer 1

सबसे पहले, दिए गए सरणी के median (यह takes linear time) ढूंढें।

फिर, केवल सरणी के माध्यम से चलें और औसत से अधिक सभी तत्वों को जोड़ दें।

गणना करें कि आपने कितने तत्वों को बुलाया (M)। यदि M < N/2, तो इसका मतलब है कि कई तत्व जो औसत मान के बराबर हैं (अर्थात्, N/2 - M) शीर्ष आधे से संबंधित हैं। अपने योग में जोड़ें कि कई औसत मूल्य। हमें इस जटिलता की आवश्यकता है क्योंकि हम नहीं जानते कि कितने औसत तत्व (कई हो सकते हैं) शीर्ष आधा से संबंधित हैं: यदि हम उन्हें सब लेते हैं, तो हम N/2 तत्वों से अधिक समेकित हो सकते हैं।

अब आपके पास सरणी के शीर्ष भाग का योग है। N/2 द्वारा विभाजित करें, और आप कर चुके हैं।

Answer 2

मैं इस सुझाव है:

उपयोग quicksort, कुछ धुरी का चयन करें। यह आपकी सूची को दो उपन्यास में विभाजित करेगा, जो पिवोट से छोटा है, उससे बड़ा एक। यदि छोटे sublist का आकार < = एन/2 है, औसत a1 औसत गणना करें।
यदि size == N/2 or size == N/2 -1
आप तुरंत कर रहे हैं।

यदि कुल आकार एन/2 तक बड़ा उपन्यास पुन: विभाजन नहीं करता है।

यदि आकार> एन/2 विभाजन छोटे sublist।

पूरा होने तक सभी को दोहराएं।

पीएस: आपको सॉर्ट करने की आवश्यकता नहीं है।

Answer 3

आप प्राथमिकता कतार का उपयोग कर सकते हैं। n, आपने कितने तत्वों को देखा है, इसकी गणना करने के लिए तत्वों को कतार में डालें। n/2 कतार से अधिकतम तत्व एक संचयक में निकालें और औसत की गणना करें।

कतार, पीछे एक अच्छी तरह से चुना डेटा संरचना के साथ

इस तरह के एक फाइबोनैचि ढेर के रूप में, यह आप, O(n log n) क्रम दे देंगे के रूप में प्रविष्टि O(1) है और निष्कर्षण O(log n) है।

दुर्भाग्यवश ओ (एन) रनटाइम नहीं जिसे आप ढूंढ रहे थे, लेकिन पहले से ही लागू डेटा संरचना के साथ, यह बहुत समझदार सीधा कोड उत्पन्न करेगा।

Answer 4

यह रैखिक समय में स्पष्ट रूप से हल करने योग्य है, यदि आप रैखिक समय में औसत पा सकते हैं। और रैखिक समय में एक औसत खोजना मुश्किल है, लेकिन संभव है। उदाहरण के लिए विकिपीडिया लेख selection algorithms पर देखें।