मेडियन-ऑफ-मेडियन एल्गोरिदम ब्लॉक आकार 3 का उपयोग क्यों नहीं कर सकता?

Question

मैं इस धारणा के तहत निर्धारिती माध्यमिक खोज के विश्लेषण के माध्यम से कार्य कर रहा हूं कि इनपुट 5 के बजाय 3 भागों में बांटा गया है और सवाल यह है कि यह कहां टूट जाता है?

का चयन करें (मैं, एन)

1. फूट डालो 5. के समूहों में n तत्वों रटना द्वारा प्रत्येक 5-तत्व समूह की माध्यिका खोजें:

   खोजने एल्गोरिथ्म

   नियतात्मक मंझला।

2. रिकर्सिव रूप से पिटोट होने के लिए medn/5⎦ समूह मध्यस्थों का औसत x चुनें।

3. पिवट एक्स के आसपास विभाजन। चलो k = रैंक (एक्स)

4. यदि मैं = तो लौट कश्मीर एक्स

elseif मैं < कश्मीर

तो रिकर्सिवली निचले हिस्से में ith सबसे छोटा तत्व का चयन करें

और बाद में (i-k) th ऊपरी भाग

मैं गुदा के माध्यम से चला गया एल्गोरिदम के ysis और मेरा मानना ​​है कि चरण 1 और 3 ओ (एन) ले जाएगा जहां यह केवल 5 तत्वों के औसत को खोजने के लिए स्थिर समय लेता है और चरण 2 टी (एन/5) लेता है। इसलिए कम से कम 3/10 तत्व ≤ पी हैं, और सरणी का कम से कम 3/10 ≥ पी है, इसलिए, चरण 4 टी (7 एन/10) होगा और पुनरावृत्ति प्राप्त होगा। टी (एन) ≤ सीएन + टी (एन/5) + टी (7 एन/10), लेकिन जब मैं तत्वों को 3 के गोरोप में विभाजित करता हूं, तो 9 तत्वों को कहें और मैंने उन्हें समूह में विभाजित किया है:

{1,2,10} {4,11,14}, {15,20,22}

मुझे औसत 2,11,20 और पी = 11 मिला।

सामान्य रूप से पांच के समूह में जी = एन/5 समूह और कम से कम ⌈g/2⌉ उनमें से (उन समूहों जिनके औसत ≤ पी हैं) कम से कम पांच तत्वों में से तीन हैं ≤ पी। इसलिए तत्वों की कुल संख्या ≤ पी कम से कम 3⌈g/2⌉ ≥ 3n/10 है। लेकिन 3 के समूह में हम सभी तीन तत्व पी से कम हो सकते हैं। और यहां मुझे लगता है कि एल्गोरिदम टूट जाएगा !!

क्या मुझे यह विचार सही मिला ???

Answer 1

3 के समूह में, 5 के समूहों के लिए, लगभग आधे समूहों में औसत माध्य मध्यस्थ से कम है, इसलिए उन समूहों में आप अपने औसत से कम तत्वों को त्याग सकते हैं। आपके मामले में, (1,2,10) में इसका औसत 11 से कम है, इसलिए आप 1 और 2 को छोड़ सकते हैं।

जहां मुझे लगता है कि 3 के समूहों के लिए चीजें टूटती हैं तो लागत में है। 3 (मंजिल (मंजिल (एन/5)/2 - 2) जो लगभग 3 एन/10 2 हो जाती है (मंजिल (मंजिल (एन/3)/2 -2) या तो, जो मोटे तौर पर एन/3 है। इसका मतलब है कि 7 एन/10 2 एन/3 हो जाता है। मंजिल (एन/5) फर्श (एन/3) बन जाती है, इसलिए 7 सीएन/10 + 2 सीएन/10 = 9 सीएन/10 के बजाय आपको केवल 2 सीएन/3 + सीएन/3 = सीएन, और टी (एन) < = सीएन के बजाय आप कुछ ऐसा करने जा रहे हैं जहां आपको उन शर्तों पर बारीकी से देखना होगा, जिनमें सी शामिल नहीं है, और आप यह दिखा सकते हैं कि यह सब के बाद रैखिक नहीं है।

ऐसा लगता है कि आप वास्तव में रिकर्सन के प्रत्येक चरण में थोड़ा और तत्वों को फेंक देते हैं, लेकिन रिकर्सन काम की मात्रा को 3 से 5 तक छोड़ देता है, और यह भी तोड़ने के लिए पर्याप्त नहीं है।