एक जंजीर हैश तालिका से एक यादृच्छिक तत्व कुशलता से उठा रहा है?

Question

बस अभ्यास के लिए (और नहीं एक होमवर्क असाइनमेंट के रूप में) मैं इस समस्या को हल करने के लिए (CLRS, 3 संस्करण, व्यायाम 11.2-6) कोशिश कर रहे हैं:

के हैश तालिका में मान लीजिए हमारे द्वारा संगृहीत n कुंजी आकार मीटर, चेनिंग द्वारा हल किए गए टकराव, और हम प्रत्येक श्रृंखला की लंबाई को जानते हैं, जिसमें सबसे लंबी श्रृंखला की लंबाई एल शामिल है। प्रक्रिया का वर्णन करें जो हैश तालिका में कुंजी के बीच यादृच्छिक रूप से एक कुंजी का चयन करता है और इसे अपेक्षित समय ओ (एल * (1 + एम/एन)) में देता है।

जो मैंने अभी तक सोचा था कि प्रत्येक कुंजी लौटाई जाने की संभावना 1/n है। यदि हम 1 से n के बीच यादृच्छिक मान x प्राप्त करने का प्रयास करते हैं, और बाल्टी में श्रृंखला के साथ बाल्टी द्वारा क्रमबद्ध क्रम में xth कुंजी को खोजने का प्रयास करें, तो यह ओ (एम) को जाकर सही बाल्टी ढूंढने के लिए ले जाएगा श्रृंखला में सही कुंजी प्राप्त करने के लिए बाल्टी के माध्यम से एक और ओ (एल) समय के माध्यम से।

Answer 1

दोहराएँ एक तत्व जब तक निम्न चरणों को लौटा दिया जाता है:

• बेतरतीब ढंग से एक बाल्टी का चयन करें। k बाल्टी में तत्वों की संख्या होने दें।
• 1 ... L से यादृच्छिक रूप से p चुनें। यदि p <= k तो बाल्टी में p वें तत्व वापस करें।

यह स्पष्ट होना चाहिए कि प्रक्रिया यादृच्छिक रूप से एक तत्व को समान रूप से लौटाती है। हम एक 2 डी सरणी में रखे तत्वों को अस्वीकृति नमूना लगाने के प्रकार हैं।

प्रति बाल्टी तत्वों की अपेक्षित संख्या n/m है। नमूना प्रयास सफल होने की संभावना (n/m)/L है। बाल्टी खोजने के लिए आवश्यक प्रयासों की अपेक्षित संख्या L * m/n है। O(L) बाल्टी से तत्व को पुनर्प्राप्त करने की लागत के साथ, अपेक्षित चलने का समय O(L * (1 + m/n)) है।