ओ (1) हैश लुक अप?

Question

मैं एक दावा में भाग गया कि हैशसेट < टी >।() एक ओ (1) ऑपरेशन है। इसने मुझे आश्चर्यचकित कर दिया क्योंकि मैंने सामना करने वाली हर चर्चा के बारे में टकराव की संभावना का उल्लेख किया है, संभावित रूप से ओ (एन) रन टाइम की ओर अग्रसर है।

उत्सुक होने के कारण, मैंने हैशसेट < टी > के लिए प्रलेखन में देखा। इसमें शामिल हैं और हैशटेबल भी शामिल हैं। दोनों विधियों के लिए प्रलेखन एक ही दावा करते हैं।

जब मैं परावर्तक में देखता हूं, हैशसेट < टी >।() को लूप के साथ कार्यान्वित किया जाता है, जिसमें स्लॉट्स की एक सूची होती है जिसमें वे हैंश होते हैं।

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

तो क्या ओ (1) दावा गलत है? या क्या मैं कुछ न कुछ भूल रहा हूं?

Answer 1

लेकिन बिग ओ नोटेशन की मेरी समझ यह है कि यह सबसे खराब मामला रनटाइम समय है, सर्वोत्तम नहीं।

दुर्भाग्य से, एल्गोरिदम का वर्णन करते समय बिग-ओ के लिए कोई "मानक" नहीं है। अक्सर, इसका उपयोग सामान्य या औसत मामले का वर्णन करने के लिए किया जाता है - सबसे खराब मामला नहीं।

Wikipedia से

:

... इस अंकन अब अक्सर भी एल्गोरिदम के विश्लेषण में कम्प्यूटेशनल संसाधनों की एक एल्गोरिथ्म के उपयोग के लिए प्रयोग किया जाता है: सबसे खराब स्थिति या औसत मामला ...

इस मामले में, यह उचित हैशिंग के मानक मानक का वर्णन कर रहा है। यदि आपके पास उचित हैशिंग है, तो सीमित व्यवहार आकार एन के लिए स्थिर रहेगा, इसलिए ओ (1)।

Answer 2

सामान्य में, यह ओ (1) है।

Answer 3

नहीं, बिग ओ "सबसे खराब मामला" परिभाषित नहीं करता है, यह एक सीमा को परिभाषित करता है। हैश-आधारित लुकअप (अच्छे हैशिंग एल्गोरिदम के साथ जो कुशल मूल्य वितरण और कम टकराव दर प्रदान करते हैं) निरंतर मूल्य की ओर बढ़ते हैं क्योंकि वस्तुओं की संख्या बढ़ जाती है (वे कभी भी पहुंच नहीं पाएंगे या निरंतर मूल्य नहीं होंगे, लेकिन यह एक सीमा है)।

Answer 4

मेरा मानना ​​है कि इसका औसत औसतन (1) है।

Answer 5

बिग ओह की मेरी समझ यह है कि "सबसे खराब मामला" आमतौर पर शामिल तत्वों की संख्या के संदर्भ में होता है। तो यदि कोई कार्य 10 तत्वों के साथ ओ (एन) निष्पादित करना था, लेकिन ओ (एन वर्ग) 100 या उससे अधिक के साथ (सुनिश्चित नहीं है कि ऐसा एल्गोरिदम वास्तव में मौजूद है), तो एल्गोरिदम को ओ (एन वर्ग) माना जाता है।

Answer 6

ओ (1) का मतलब "सबसे खराब मामला" नहीं है। हैश के लिए, आमतौर पर कहता है कि "अपेक्षित" लुकअप समय ओ (1) है, क्योंकि हैश टकराव की संभावना कम है।

Answer 7

एक उचित ढंग से लागू हैश तालिका के लिए, देखो अप amortized निरंतर समय जटिलता है।

प्रैक्टिस में, टकराव के मामले में एक एकल रूप ओ (एन) हो सकता है, जैसा कि आप कहते हैं। हालांकि, यदि आप बड़ी संख्या में लुकअप करते हैं तो प्रति ऑपरेशन औसत समय जटिलता निरंतर है।

का हवाला देते हुए विकिपीडिया:

परिशोधित विश्लेषण से कि संभावना में औसत दर-मामला प्रदर्शन शामिल नहीं है अलग है, अमूर्त विश्लेषण सबसे खराब मामले प्रदर्शन पर प्रति ऑपरेशन के समय की गारंटी देता है।

विधि को ज्ञान की आवश्यकता है कि कौन सी श्रृंखला संचालन संभव है। डेटा संरचनाओं के साथ यह आमतौर पर मामला है, जिसमें राज्य है जो संचालन के बीच बनी रहती है। मूल विचार यह है कि एक सबसे खराब केस ऑपरेशन राज्य को इस तरह से बदल सकता है कि सबसे खराब मामला लंबे समय तक फिर से नहीं हो सकता है, इस प्रकार इसकी लागत "अमूर्त" हो जाती है।

Answer 8

नहीं, बिग-ओ नोटेशन सबसे खराब स्थिति तक सीमित नहीं है। आम तौर पर आप बिग-ओ को सर्वश्रेष्ठ मामले, औसत-मामले और सबसे बुरे मामले के लिए प्रकाशित करेंगे। यह सिर्फ इतना है कि ज्यादातर लोग सबसे बुरे मामले पर ध्यान केंद्रित करते हैं। हैश टेबल के मामले में छोड़कर सबसे खराब मामला शायद ही कभी होता है इसलिए औसत-मामले का उपयोग करना अधिक उपयोगी होता है।

हां, एक अच्छा हैश फ़ंक्शन टकराव की संभावना को कम कर देता है। एक खराब हैश फ़ंक्शन क्लस्टरिंग प्रभाव का कारण बन सकता है (जहां अलग-अलग मान सटीक समान मान या उसी मान के करीब हैं)। यह प्रदर्शित करना आसान है कि HashSet वास्तव में GetHashCode फ़ंक्शन को इस तरह से कार्यान्वित करके ओ (एन) बन सकता है कि यह हर समय एक ही मूल्य देता है।

एक पोषक तत्व में, हाँ HashSet और Dictionary को ओ (1) रनटाइम जटिलता के रूप में वर्णित किया जा सकता है क्योंकि औसत-मामले परिदृश्य पर जोर दिया जाता है।

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

Answer 9

हैश तालिकाओं में न केवल औसत-केस प्रदर्शन ओ (1) है, लेकिन यदि हैश फ़ंक्शन यादृच्छिक है, तो किसी दिए गए प्रतिशत के लिए पी < 100%, प्रदर्शन जिसे प्राप्त किया जा सकता है, ठीक से- डिजाइन हैश कहानी ओ (1) है। यद्यपि चरम परजीवी मामले एन बढ़ने के रूप में अधिक से अधिक गंभीर हो जाते हैं, यह इस तथ्य से संतुलित है कि मामूली-परजीवी मामलों में भी कम और कम संभावना होती है।