यादृच्छिक quicksort: दो तत्वों की तुलना की संभावना?

Question

मैं एम। मिट्टनमेकर और ई। अपफल द्वारा "Probability and Computing" पढ़ रहा हूं। मुझे समझ में समस्या है कि दो तत्वों की तुलना की संभावना की गणना कैसे की जाती है।

इनपुट: अनुसार क्रमबद्ध सूची (y1, y2, ..., Yn) नंबर की। हम पिवट तत्व (यादृच्छिक रूप से) की तलाश में हैं। प्रश्न: संभावना क्या है कि दो तत्व यी और वाईजे (जे> i) की तुलना की जाएगी?

उत्तर (किताब से): यी और yj तुलना में किया जाएगा यदि या तो यी या yj अनुक्रम से पहले ड्रा में धुरी के रूप में चयन किया जाएगा (, यी, यी +1 ..., yj -1, yj) । तो संभावना है: 2/(जे-आई + 1)।

मेरे लिए समस्या प्रारंभिक दावा है: उदाहरण के लिए, पूरे सूची से पहले ड्रा में यी उठा yj (और इसके विपरीत) के साथ तुलना का कारण होगा और संभावना 2/n है।

तो, बल्कि "रिवर्स" दावा सत्य है - वाई (yi + 1, ..., yj-1) तत्वों में से कोई भी yi या yj से पहले नहीं चुना जा सकता है, लेकिन "पूल" आकार निश्चित नहीं है (पहले ड्रा में यह निश्चित रूप से एन है, लेकिन दूसरे पर यह छोटा है)।

क्या कोई यह बता सकता है कि लेखक इस तरह के एक सरल निष्कर्ष के साथ कैसे आते हैं?

संपादित 1: कुछ अच्छी आत्मा ने मेरी पोस्ट पॉलिश की, धन्यवाद :-)।

संपादित 2: सूची प्रारंभ में क्रमबद्ध है।

Answer 1

लेखकों द्वारा दिए गए उत्तर सही हैं, हालांकि मैं अभी भी नहीं देखता कि वे आसानी से और तेज़ निष्कर्ष पर कैसे पहुंचे।

एल = जे-आई + 1 द्वारा इंगित करते हैं। जे के वास्तविक मूल्यों और मैं बात यहाँ नहीं है, क्या मायने रखती है एल Let भी पी (एन, एल) आकार एन की संख्या

तथ्य का आदेश दिया अनुक्रम से यी और yj तत्व की तुलना की संभावना से निरूपित है:

• पी (एन, 2) = 1
• पी (एन, एल) = 2/एन 1/एन * (पी (एन -1, एल) + P (एन -2, एल) + पी (एन -3, एल) + ... + पी (एल, एल))

यह योग बदसूरत दिखता है, लेकिन दो परीक्षणों के बाद ऐसा लगता है कि पी (एन, एल) शायद 2 के बराबर है/एल। इसे बाहर की जाँच करते हैं:

• पी (एन, एल = 2) = 1 = 2/2 = 2/एल
• के पी (एन, एल) = 2/एल
• पी मान लें (एन + 1, एल) = 2/(एन + 1) + 1/(एन + 1) * (पी (एन, एल) + ... पी (एल, एल)) = 2/(एन + 1) + (एन-एल + 1) * 1/(एन + 1) * 2/एल = 2/एल

और चूंकि एल = जे-आई + 1, हमें 2/(जे-आई + 1) मिलता है।

Answer 2

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

प्रत्येक चरण में, पिवट को अनुक्रम (yi, yi+1, ..., yj) से चुना जाता है। इस अनुक्रम में कितने तत्व हैं? j - i + 1 (मुझे लगता है कि आपके पास एक टाइपो था, यह y - i + 1 नहीं हो सकता है)।

तो इस सूची से दो विशिष्ट तत्वों में से एक को चुनने की संभावना स्पष्ट रूप से 2/(j - i + 1) है।

मेरे लिए समस्या प्रारंभिक दावा है: उदाहरण के लिए, पूरी सूची से पहले ड्रॉ में yi उठाकर yj (और इसके विपरीत) की तुलना में संभावना होगी और संभावना 2/n है।

yi चुनने से इसकी तुलना अन्य j - i तत्वों से की जा सकती है। आपको n कहां से मिला? याद रखें कि आपकी सूची केवल yi से yj पर जाती है!

संपादित:

सवाल फिर से पढ़ना, मैं यह थोड़ा अस्पष्ट मिल रहा है। रिकर्सन के पहले चरण में दो तत्व की तुलना करने की संभावना 2/n है जैसा कि आप कहते हैं, क्योंकि i और j1 और n हैं। एक अज्ञात रिकर्सिव चरण पर दो तत्व की तुलना करने की संभावना मैंने ऊपर वर्णित की है।