मुझे पता है कि ओ (एन) में संख्याओं की सूची के माध्य की गणना करना संभव है। लेकिन औसत के बारे में क्या? क्या सॉर्ट (ओ (एन लॉग एन)) से कोई बेहतर एल्गोरिदम है और लुकअप मध्य तत्व (या दो मध्यम तत्वों का मतलब यदि सूची में आइटम की संख्या भी है)?क्या ओ (एन लॉग एन) से बेहतर संख्याओं की सूची के औसत की गणना करना संभव है?
यह लिंक हाल ही में औसत की गणना करने के लिए पॉप अप किया गया है: http://matpalm.com/median/question.html।
सामान्यतः मुझे लगता है कि आप ओ (एन लॉग एन) समय से आगे नहीं जा सकते हैं, लेकिन मेरे पास इसका कोई सबूत नहीं है :)। इससे कोई फर्क नहीं पड़ता कि आप इसे समानांतर बनाते हैं, परिणामों को एक ही मान में एकत्रित करने से कम से कम लॉग एन निष्पादन के स्तर होते हैं।
मैंने अपना उत्तर "ओ (लॉग एन)" से "ओ (एन लॉग एन)" में बदल दिया है, जो आप सोच रहे थे, मुझे लगता है, प्रश्न और बाकी का जवाब दिया गया है। – Beska
संख्या असतत (जैसे पूर्णांक) कर रहे हैं और वहाँ विशिष्ट मानों की एक प्रबंधनीय संख्या है, तो आप एक "बाल्टी प्रकार" जो हे है (एन) का उपयोग कर सकते, तो आंकड़ा करने के लिए बाल्टी से अधिक पुनरावृति बाहर कौन सा बाल्टी मध्यस्थ रखती है। पूर्ण गणना ओ (एन) समय में और ओ (बी) अंतरिक्ष में है।
आप किस बारे में बात कर रहे हैं selection algorithm है, जहां k = n/2 है। Quicksort में प्रयुक्त एक ही विभाजन कार्य के आधार पर एक विधि है जो काम करता है। इसे आश्चर्यजनक रूप से नहीं कहा जाता है, quickselect। हालांकि, यह क्विकॉर्ट की तरह हो सकता है, ओ (एन) सबसे खराब मामला है, इसे proper pivot selection का उपयोग करके रैखिक समय में लाया जा सकता है।
आंशिक रूप से अप्रासंगिक, लेकिन: वेब पर इस तरह के सामान्य मूल प्रश्नों के उत्तर तुरंत प्राप्त करने के तरीके पर एक त्वरित युक्ति।
नमूना मंझला के कुशल गणना
यहां तक कि एन आइटम छँटाई (एन लॉग इन करें n) संचालन, सामान्य हे में ले जाता है का उपयोग करके, हालांकि एक "विभाजित और जीत" एल्गोरिदम एन वस्तुओं के औसत को केवल ओ (एन) संचालन के साथ गणना की जा सकती है (वास्तव में, आप हमेशा इस विधि के साथ मूल्यों की सूची के के-वें तत्व को पा सकते हैं; इसे selection problem कहा जाता है) ।
... सबसे बुरी स्थिति रैखिक समय चयन एल्गोरिदम हैं। ...
बस मज़ेदार (और कौन जानता है, यह तेज़ हो सकता है) एक और यादृच्छिक औसत एल्गोरिदम है, जो कि मिट्टनमेकर और अपफॉल की पुस्तक में तकनीकी रूप से समझाया गया है। असल में, आप सूची का बहुपद रूप से छोटा सबसेट चुनते हैं, और (कुछ फैंसी बुकवर्क के साथ) जैसे कि इसमें वास्तविक औसत शामिल है, और उसके बाद असली औसत खोजने के लिए इसका उपयोग करें। पुस्तक Google पुस्तकें पर है, और यहां एक link है।नोट: मैं algorthm के पृष्ठों को पढ़ने में सक्षम था, इसलिए यह मानते हुए कि Google पुस्तकें सभी को एक ही पृष्ठ दिखाती हैं, आप उन्हें भी पढ़ सकते हैं।
यह एक यादृच्छिक एल्गोरिदम एसटी है। यदि यह उत्तर पाता है, तो यह 100% निश्चित है कि यह सही उत्तर है (इसे लास वेगास शैली कहा जाता है)। यादृच्छिकता रनटाइम से उत्पन्न होती है --- कभी-कभी (संभाव्यता 1/(वर्ग (एन)) के साथ, मुझे लगता है) यह औसत खोजने के लिए विफल रहता है, और फिर से चलाना चाहिए।
असम्बद्ध रूप से, जब आप विफलता का मौका लेते हैं तो यह बिल्कुल रैखिक होता है --- यह कहना है कि यह रैखिक से थोड़ा कम है, ठीक उसी तरह जब आप ध्यान में रखते हैं कि आपको कितनी बार आवश्यकता हो सकती है इसे फिर से चलाने के लिए, यह रैखिक हो जाता है।
नोट: मैं यह नहीं कह रहा कि यह बेहतर या बदतर है --- मैंने निश्चित रूप से इन एल्गोरिदम के बीच वास्तविक जीवन रनटाइम तुलना नहीं की है! मैं बस एक अतिरिक्त एल्गोरिदम प्रस्तुत कर रहा हूं जिसमें रैखिक रनटाइम है, लेकिन यह काफी अलग तरीके से काम करता है।
दिलचस्प सामान! –
यादृच्छिक एल्गोरिदम का प्रयास करें, नमूना आकार (उदा। 2000) डेटा आकार एन से स्वतंत्र है, फिर भी पर्याप्त उच्च (99%) सटीकता प्राप्त करने में सक्षम हो। यदि आपको उच्च सटीकता की आवश्यकता है, तो नमूना आकार बढ़ाएं। चेरनॉफ बाध्य का उपयोग करके एक निश्चित नमूना आकार के तहत संभावना का सबूत हो सकता है। मैंने एल्गोरिदम को लागू करने के लिए कुछ जावास्क्रिप्ट कोड लिखा है, इसे लेने में संकोच न करें। http://www.sfu.ca/~wpa10
वह लिंक "मध्यस्थों के मध्य" के बारे में बात करता है, या दूसरे शब्दों में, "सत्य" औसत का अनुमान। मुझे यकीन नहीं है कि ओपी क्या मांग रहा है। –
निर्धारिती चयन का उपयोग करके आप असली औसत प्राप्त करते हैं। यहां देखें: http://en.wikipedia.org/wiki/Selection_algorithm – Anna
मुझे लगता है कि पेस्टो ने इसे पहले ही लिखा है। – Anna