क्विकॉर्ट और सम्मिलन सॉर्ट हाइब्रिड अपेक्षित चलने का समय

Question

मैं स्वयं सीएलआरएस तीसरा संस्करण सीख रहा हूं और यहां एक कठिन प्रश्न है जिसमें मैंने का जवाब दिया है, इसके उत्तर के साथ सभी के लिए एक सेवा के रूप में।

7.4-5 हम प्रविष्टि के समय तेजी से चल रहा है का लाभ लेने तरह जब अपने इनपुट है "लगभग" अनुसार क्रमबद्ध द्वारा व्यवहार में quicksort का चलने का समय बढ़ा सकते हैं। को k तत्वों के साथ एक उपरायरे पर क्विकॉर्ट पर कॉल करने पर, इसे आसानी से बिना सबएरे को सॉर्ट करने दें। क्विकसॉर्ट रिटर्न के लिए शीर्ष-स्तरीय कॉल के बाद, सॉर्टिंग प्रक्रिया को समाप्त करने के लिए संपूर्ण सरणी पर सम्मिलन क्रम चलाएं। तर्क दें कि इस सॉर्टिंग एल्गोरिदम O(nk+nlg(n/k)) अपेक्षित समय में चलता है। हमें k को सिद्धांत और अभ्यास में दोनों को कैसे चुनना चाहिए?

Answer 1

यदि आप समीकरण nlgn > nk + nlog(n/k) को विकसित करते हैं तो आपको log k > k मिलता है। जो असंभव है। इसलिए सिद्धांत में यह संभव नहीं है। लेकिन अभ्यास में सम्मिलन क्रम और quicksort के साथ लगातार कारक शामिल हैं। इस pdf में चर्चा किए गए समाधान पर नज़र डालें। आप अपना उत्तर अपडेट करना चाहेंगे। ।

Answer 2

एक पत्ती की 1 से k के बीच आकार की समान संभावना है।
तो पत्ती का अनुमानित आकार k/2 है।
यदि पत्ते का अनुमानित आकार k/2 है तो हम n/(k/2)=(2n)/k ऐसी पत्तियों की अपेक्षा करते हैं।
सादगी के लिए कहें कि हम n/k ऐसी पत्तियों की अपेक्षा करते हैं और प्रत्येक पत्ते का अपेक्षित आकार k है।
INSERTION-SORT का अनुमानित समय O(n^2) है।
हमने पाया कि अभ्यास में 5.2-5 और समस्या 2-4 सी।
तो INSERTION-SORT उपयोग की अपेक्षित चलती समय O((n/k)*(k^2))=O(nk) है।
यदि हम उम्मीद करते हैं कि हमारे विभाजन समूह k आकार के हों तो रिकर्सन पेड़ की ऊंचाई lgn-lgk=lg(n/k) होने की उम्मीद है क्योंकि हम पहले lgk को रोकने की उम्मीद करते हैं।
रिकर्सन पेड़ के प्रत्येक स्तर पर O(n) संचालन हैं।
जो हमें O(nlg(n/k)) पर ले जाता है।
हम निष्कर्ष निकालते हैं कि अपेक्षित चलने का समय O(nk+nlg(n/k)) है।

सिद्धांत रूप में, हमें k=lgn चुनना चाहिए, इस तरह से हमें O(nlgn) का सबसे अच्छा चलने वाला समय मिलता है।

प्रैक्टिस में, हमें klgn के मानों में से एक में चुनना चाहिए जो हमें RANDOMIZED-QUICKSORT चलाने से बेहतर प्रदर्शन देता है।

उत्तर का दूसरा भाग बड़े-ओ नोटेशन का उपयोग बहुत कम करता है, इसलिए k की अधिक सटीक चुनने के लिए, कृपया अंकुश द्वारा दूसरे उत्तर में दिए गए लिंक का पालन करें।

Answer 3

दरअसल, उत्तर k = 8 है।

आपको प्राप्त एल्गोरिदम दो अज्ञात कार्यों की संरचना है, जिनमें से एक O(nk) है और दूसरा O(n lg n/k) है। वे अज्ञात कार्य औसत केस स्थिरांक छुपाते हैं। औसत मामले में n^2/4 समय में सम्मिलन क्रम चलता है और यादृच्छिक Quicksort औसत मामले में 1.386 n lg n में चलता है। हम k का मान खोजना चाहते हैं जो nk/4 + 1.386(n lg n/k) के मान को कम करता है जो nk/4 + 1.386 n lg n - 1.386 n lg k के बराबर है। इसका मतलब है कि अधिकतम कार्य 1.386 lg k - k/4 ढूंढना है। वह अधिकतम मान k = 8 पर होता है।