औसत चयन के इष्टतम औसत - 3 तत्व ब्लॉक बनाम 5 तत्व ब्लॉक?

Question

मैं एक अच्छा पिवट तत्व चुनने के लिए the Select algorithm पर आधारित एक त्वरित-संस्करण कार्यान्वयन पर काम कर रहा हूं। परंपरागत ज्ञान सरणी को 5-तत्व ब्लॉक में विभाजित करना प्रतीत होता है, प्रत्येक का औसत लेता है, और उसके बाद परिणामस्वरूप औसत लोगों को "मध्यस्थों का औसत" प्राप्त करने के लिए समान अवरोध दृष्टिकोण लागू करता है।

मुझे भ्रमित करने वाला क्या है 3-तत्व ब्लॉक के बजाय 5-तत्व ब्लॉक की पसंद है। 5-तत्व ब्लॉक के साथ, मुझे लगता है कि आप n/4 = n/5 + n/25 + n/125 + n/625 + ... मेडियन-ऑफ -5 ऑपरेशंस करते हैं, जबकि 3-तत्व ब्लॉक के साथ, आप n/2 = n/3 + n/9 + n/27 + n/81 + ... मध्य-ऑफ-3 ऑपरेशंस करते हैं। चूंकि प्रत्येक औसत -5 -5 की तुलना 6 तुलना होती है, और प्रत्येक औसत-3-3 की तुलना 2 तुलना होती है, जिसके परिणामस्वरूप 3*n/2 औसत-से -5 और n माध्यमिक-3 का उपयोग करके तुलनाओं की तुलना में तुलना करता है।

क्या कोई इस विसंगति को समझा सकता है, और 5-तत्व ब्लॉक का उपयोग करने के लिए प्रेरणा क्या हो सकती है? मैं इन एल्गोरिदम को लागू करने के लिए सामान्य प्रथाओं से परिचित नहीं हूं, इसलिए हो सकता है कि आप कुछ कदम उठा सकें और फिर भी एक अच्छा पिवट सुनिश्चित करने के लिए औसत के लिए "पर्याप्त बंद करें" प्राप्त करें, और यह दृष्टिकोण 5-तत्व ब्लॉक के साथ बेहतर काम करता है ?

Answer 1

कारण यह है कि 3 के ब्लॉक चुनकर, हम ओ (एन) समय एल्गोरिदम होने की गारंटी खो सकते हैं।

5 के ब्लॉक के लिए, समय जटिलता है

टी (एन) = टी (एन/5) + T (7n/10) + O (एन)

3 के ब्लॉक के लिए, यह बाहर आता है

टी (एन) = टी (एन/3) + T (2n/3) + O (एन)

चेक बाहर इस: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

Answer 2

मेरा मानना ​​है कि यह करने के लिए है एक "अच्छा" विभाजन सुनिश्चित करने के साथ। 5-तत्व ब्लॉक में विभाजित करने से 70-30 का सबसे खराब-मामला विभाजित होता है। मानक तर्क इस प्रकार है: n/5 ब्लॉक, कम से कम मध्यस्थों में से आधे> = मध्यस्थ हैं, इसलिए कम से कम n/5 ब्लॉक में से कम से कम 3 तत्व (5 में से 1/2)> = औसत मध्यस्थ, और यह 3n/10 विभाजन देता है, जिसका अर्थ है कि दूसरा विभाजन सबसे खराब स्थिति में 7n/10 है।

जो T(n) = T(n/5) + T(7n/10) + O(n) देता है।

n/5 + 7n/10 < 1 के बाद से, सबसे खराब स्थिति चलने का समय ओ (एन) है।

3-तत्व ब्लॉक का चयन यह इस प्रकार है: n/3 ब्लॉक के कम से कम आधा कम से कम 2 तत्व> = मंझला के- माध्यिकाओं, इसलिए यह एक n/3 विभाजन देता है, या सबसे खराब स्थिति में 2n/3।

जो T(n) = T(n/3) + T(2n/3) + O(n) देता है।

इस मामले में, n/3 + 2n/3 = 1, इसलिए यह सबसे खराब मामले में ओ (एन लॉग एन) तक कम हो जाता है।

Answer 3

आप आकार 3 के ब्लॉक का उपयोग कर सकते हैं! हाँ, मैं आश्चर्यचकित हूं जैसे आप हैं। 2014 में (आपने 2010 में पूछा था) वहां एक पेपर आया जो दिखाता है कि ऐसा कैसे करें।

विचार इस प्रकार है: के बजाय करने का median3, partition, median3, partition, ..., है न median3, median3, partition, median3, median3, partition, ...। पेपर में इसे "दोहराया चरण एल्गोरिदम" कहा जाता है।

तो बजाय:

T(n) <= T(n/3) + T(2n/3) + O(n) 
T(n) = O(nlogn) 

एक हो जाता है:

T(n) <= T(n/9) + T(7n/9) + O(n) 
T(n) = Theta(n) 

कहा लेख Select with Groups of 3 or 4 Takes Linear Time लालकृष्ण चेन और ए डुमिट्रेस्कु (2014, arXiv), या Select with groups of 3 or 4 (2015, लेखक का कर रहा है मुखपृष्ठ)।

पीएस: ए 0 अलेक्जेंड्रेस्कू (डी भाषा प्रसिद्धि!) द्वारा Fast Deterministic Selection जो दिखाता है कि उपरोक्त को और अधिक कुशलता से कैसे कार्यान्वित किया जाए।