c# - शनर - कुंजी ओ(1) द्वारा किसी शब्दकोश के एक तत्व तक पहुंच क्यों है, भले ही हैश फ़ंक्शन ओ(1) न हो?




शब्दकोश हिन्दी से अंग्रेजी (6)

HashFunc ही परदे के पीछे बहुत सारे ऑपरेशन होते हैं

यह निश्चित रूप से सच है। हालाँकि, इन परिचालनों की संख्या कुंजी के आकार पर निर्भर करती है, न कि हैश तालिका के आकार पर, जिसमें कुंजी डाली जाती है: हैश फ़ंक्शन की गणना करने के लिए संचालन की संख्या दस या दस के साथ एक तालिका में कुंजी के लिए समान है दस हजार प्रविष्टियों के साथ।

इसीलिए हैश फ़ंक्शन की कॉल को अक्सर O (1) माना जाता है। यह फिक्स्ड-साइज़ कीज़ (इंटीग्रल वैल्यूज़ और फिक्स्ड-लेंथ स्ट्रिंग्स) के लिए ठीक काम करता है। यह एक व्यावहारिक ऊपरी सीमा के साथ चर-आकार की कुंजी के लिए एक सभ्य सन्निकटन भी प्रदान करता है।

आम तौर पर, हालांकि, हैश टेबल का एक्सेस समय O (k) है, जहां k हैश कुंजी के आकार की ऊपरी सीमा है।

मैं देख रहा हूँ कि आप किस तरह से कुंजी द्वारा अपने संग्रह तक पहुँच सकते हैं। हालाँकि, हैश फंक्शन में परदे के पीछे बहुत सारे ऑपरेशन होते हैं, है ना?

मान लें कि आपके पास एक अच्छा हैश फ़ंक्शन है, जो बहुत ही कुशल है, फिर भी कई ऑपरेशन हो सकते हैं।

क्या यह समझाया जा सकता है?


इसका मतलब यह है कि आपके संग्रह का आकार चाहे जितना भी हो, फिर भी उसके किसी भी सदस्य को पुनः प्राप्त करने में लगभग उतना ही समय लगेगा।

तो दूसरे शब्दों में 5 सदस्यों के साथ शब्दकोश में कहेंगे कि उनमें से किसी एक का उपयोग करने के लिए क़रीब 0.002 एमएस लें, साथ ही 25 सदस्यों के शब्दकोश में भी कुछ ऐसा ही होना चाहिए। बिग ओ का अर्थ है वास्तविक विवरणों या निष्पादित कार्यों के बजाय संग्रह आकार पर एल्गोरिथम जटिलता


कृपया देखें कि "O (1) एक्सेस टाइम" का क्या अर्थ है?

एक हैश फ़ंक्शन में संचालन की संख्या तब तक अप्रासंगिक है जब तक कि संग्रह में हर तत्व के लिए समान (निरंतर) समय लगता है। उदाहरण के लिए, 2 तत्वों के संग्रह में एक तत्व तक पहुँचने में .001 एमएस लगता है, लेकिन 2,000,000,000 तत्वों के संग्रह में एक तत्व तक पहुँचने में .001 एमएस लगता है। हालांकि हैश फंक्शन में सैकड़ों स्टेटमेंट और कई कैलकुलेशन हो सकते हैं।


डॉक्स से:

इसकी कुंजी का उपयोग करके किसी मूल्य को प्राप्त करना बहुत तेज़ है, O (1) के करीब है, क्योंकि T: System.Collections.Generic.Dictionary`2 वर्ग हैश टेबल के रूप में लागू किया गया है।

तो यह O (1) हो सकता है लेकिन धीमा हो सकता है। यहां आप हैशटेबल प्रदर्शन के बारे में एक और धागा पा सकते हैं: हैश टेबल - यह सरणियों से तेज क्यों है?


सैद्धांतिक रूप से यह अभी भी O (n) है, क्योंकि सबसे खराब स्थिति में आपके सभी डेटा समरूप हैश को समाप्त कर सकते हैं और एक साथ बंडल किया जा सकता है जिस स्थिति में आपको रैखिक रूप से इन सभी के माध्यम से जाना होगा।


O(1) मतलब तुरंत नहीं है। डेटा के आकार के संबंध में O(1) अर्थ है निरंतर। हैश फंक्शन में एक निश्चित समय लगता है, लेकिन उस समय की मात्रा संग्रह के आकार के साथ नहीं होती है।





big-o