हैश टकराव रैखिक जांच चलने का समय

Question

मैं एक दोस्त के साथ होमवर्क करने की कोशिश कर रहा हूं और एक प्रश्न रैखिक जांच विधि के लिए खोज, जोड़ने और हटाने के औसत चलने का समय पूछता है। मुझे लगता है कि यह ओ (एन) है क्योंकि इसे कुछ नोड्स पर जांचना है जब तक कि इसे जोड़ने के लिए एक खुलासा न हो जाए। और जब इसे खोजना मूल सूचकांक से शुरू होता है और जब तक वांछित संख्या नहीं मिल जाती तब तक चलता है। लेकिन मेरे दोस्तों का कहना है कि यह ओ (1) है। कौनसा सही हैं?

Answer 1

जब हम एसिम्प्टोटिक जटिलताओं के बारे में बात करते हैं तो हम आम तौर पर बहुत बड़े खाते में ध्यान देते हैं। अब हैश टेबल में टकराव हैंडलिंग के लिए कुछ तरीकों में जंजीर हैशिंग & रैखिक जांच है। दोनों मामलों में दो चीजें हो सकती हैं (इससे आपके प्रश्न का उत्तर देने में मदद मिलेगी): 1. आपको पूर्ण होने के कारण हैश तालिका का आकार बदलने की आवश्यकता हो सकती है 2. टकराव हो सकता है।

सबसे बुरी स्थिति में यह इस बात पर निर्भर करेगा कि आपने अपनी हैश तालिका कैसे कार्यान्वित की है, रैखिक जांच में कहें कि आपको संख्या नहीं मिलती है, आप आगे बढ़ते रहते हैं और जिस नंबर पर आप खोज रहे थे वह अंत में था। यहां ओ (एन) सबसे खराब केस चलने का समय आता है। जंजीर हैशिंग तकनीक पर आना, जब टकराव होता है, उन्हें संभालने के लिए कहते हैं कि हमने एक संतुलित बाइनरी पेड़ में चाबियाँ जमा की हैं, इसलिए सबसे खराब केस चलने का समय ओ (लॉग एन) होगा।

अब सबसे अच्छा मामला चलने का समय आ रहा है, मुझे लगता है कि कोई भ्रम नहीं है, किसी भी मामले में यह ओ (1) होगा।

ओ (एन) सबसे खराब स्थिति में होगा और अच्छी तरह से डिज़ाइन की गई हैश तालिका के औसत मामले में नहीं होगा। यदि यह औसत केस हैश टेबल में हो रहा है, तो डेटा संरचनाओं में कोई स्थान नहीं मिलेगा क्योंकि तब औसत पर संतुलित पेड़ आपको हमेशा ओ (लॉग एन) देंगे और उस पर भी ऑर्डर को सुरक्षित रखेगा।

यह कहने के लिए खेद है लेकिन दुर्भाग्य से आपका मित्र सही है। आपका मामला सबसे खराब स्थिति परिदृश्यों में होगा।

भी अधिक सूचनात्मक सामान अर्थात परिशोधित प्रसारण समय के लिए यहाँ देखो: Time complexity of Hash table