ओ (लॉग एन)

Question

में मध्यस्थ खोजें, प्रश्न यह है कि हम ओ (लॉग एन में) पूर्णांक मानों की एक प्राप्त स्ट्रीम (जैसे 12, 14, 252, 243, 15 औसत 15) के मध्य प्राप्तकर्ता को कैसे प्राप्त कर सकते हैं।) जहां एन मूल्यों की संख्या है। कृपया ध्यान दें कि हमारे पास पूर्णांक मानों की एक धारा है, इसलिए प्रत्येक मान प्राप्त करके, हमें औसत को फिर से ढूंढना होगा।

उदाहरण:

| Input | median 
1 | 12 | 12 
2 | 14 | 13 = (12+14)/2 
3 | 252 | 14 
. 
. 
. 

पी.एस: इस कलन विधि का उपयोग एक छवि को छानने हो सकता है का एक उदाहरण।

Answer 1

ठीक है, प्रश्न के अपडेट के साथ, इसलिए इरादा स्पष्ट है (न केवल औसत पाएं, लेकिन हर बार जब आप एक नया नंबर प्राप्त करते हैं तो औसत प्राप्त करें), मुझे लगता है कि एक तरीका है।

मैं ढेर की एक जोड़ी से शुरू करूंगा: अधिकतम-ढेर और एक न्यूनतम ढेर। न्यूनतम ढेर में औसत से बड़ी संख्याएं होती हैं, और औसत से अधिकतम संख्या में ढेर होता है। जब आप पहली संख्या प्राप्त करते हैं, तो यह आपका औसत है। जब आप दूसरा प्राप्त करते हैं, तो आप दोनों में से छोटे को अधिकतम-ढेर में डाल देते हैं, और दोनों में से बड़े को न्यूनतम-ढेर में डाल दिया जाता है। औसत तब न्यूनतम-ढेर पर सबसे छोटा होता है, और अधिकतम-ढेर पर सबसे बड़ा होता है।

दो ढेर के साथ, आप एक सिंगल इंटीजर के लिए स्टोरेज चाहते हैं जो इनपुट की अजीब संख्या प्राप्त करने पर वर्तमान औसत होगा। आप इसे काफी सरलता से पॉप्युलेट करेंगे: यदि आप वर्तमान में इसके साथ एक इनपुट प्राप्त करते हैं, तो आप मूल रूप से उन दो वस्तुओं (नई संख्या और पुरानी औसत) को सॉर्ट करते हैं और छोटी वस्तुओं के लिए ढेर में छोटे डालते हैं, और ढेर में बड़े होते हैं बड़ी वस्तुओं के लिए। आपका नया माध्य तब उन दो ढेर के आधारों का मतलब होगा (और आप अन्य स्टोरेज स्थान को खाली के रूप में चिह्नित करेंगे)।

जब आप उस खाली के साथ एक नया नंबर प्राप्त करते हैं, तो आप नए नंबर की तुलना मध्यस्थ से करेंगे। यदि यह ढेर के आधार के रूप में संख्याओं के बीच है, तो यह नया औसत है, और आप कर चुके हैं।अन्यथा, उस आधार से संख्या निकालें जो औसत को पकड़ लेना चाहिए (बड़ी संख्या यदि बड़ी संख्या बड़ी हो, तो छोटी हो तो छोटी हो) और उसे मध्य स्थान में रखें, फिर उस नंबर से ढेर में नया नंबर डालें।

कम से कम अगर स्मृति कार्य करता है, तो एक ढेर में निकालने/डालने से ओ (लॉग एन) होना चाहिए। मेरा मानना ​​है कि इसमें शामिल सभी चीजें निरंतर जटिलता होनी चाहिए।

Answer 2

(मैं, मान लें कि आप एक एल्गोरिथ्म है कि, n मौजूदा संख्या और एक नया नंबर दिया के बाद कर रहे हैं, लघुगणक समय लगेगा n + 1 संख्या के नए संग्रह की औसत खोजने के लिए करेंगे ताकि n जोड़कर मिलने की कुल चालू अवधि हो जाएगा O (n एलजी n))

वहाँ शायद पहले से ही इसके लिए एक नाम दिया है एल्गोरिथ्म है, लेकिन यहाँ मेरा विचार है:। एक लाल-काले वृक्ष जिसमें आप सम्मिलित बनाए रखें जैसे ही वे पहुंचते हैं। प्रत्येक नोड में, संख्या स्वयं और बच्चे/अभिभावक पॉइंटर्स के अतिरिक्त, आप एक पूर्णांक संग्रहीत करते हैं जो इस नोड के नीचे मौजूद नोड्स की संख्या बताता है (सुविधा के लिए नोड स्वयं सहित)। मुझे पूरा यकीन है कि इस जानकारी को प्रत्येक सम्मिलन ऑपरेशन पर लॉगरिदमिक समय में अपडेट किया जा सकता है, भले ही वृक्षारोपण की आवश्यकता हो। पेड़ में एम्बेडेड इस जानकारी के साथ, मध्यस्थ को ढूंढना लॉगरिदमिक समय में किया जा सकता है यदि आप पेड़ में नोड्स की संख्या का भी ट्रैक रखते हैं।

(यह एक से थोड़ा भी उच्च स्तर का वर्णन हो सकता है, यदि आप अधिक जानकारी की आवश्यकता मुझे पता है।)

Answer 3

Hoare's selection algorithm (उर्फ quickselect) हे में (एन) औसत समय ऐसा कर सकते हैं।

यह मूल रूप से एक यादृच्छिक पिवट के साथ डेटा सेट को विभाजित करता है और उचित भाग की जांच करता है। एक median of medians algorithm भी है जिसने ओ (एन) सबसे खराब समय जटिलता की गारंटी दी है, लेकिन सामान्य उपयोग के लिए यह आमतौर पर एक ओवरकिल होता है।