जो अधिक समय लेगा?बिश ओ ऑफ हैश टेबल बनाम बाइनरी सर्च ट्री
सॉर्ट किए गए क्रम में बाइनरी खोज पेड़ में संग्रहीत सभी आइटम प्रिंट करें या क्रमबद्ध क्रम में हैश तालिका में संग्रहीत सभी आइटम प्रिंट करें।
क्रमबद्ध क्रम में हैश तालिका के आइटम मुद्रित करने में अधिक समय लगेगा क्योंकि हैश तालिका को कभी भी सही नहीं किया गया है? और एक बीएसटी है?
आप सही हैं। हैशटेबल को कुछ हैश फ़ंक्शन द्वारा क्रमबद्ध किया जाता है, न कि उनके प्राकृतिक सॉर्ट ऑर्डर द्वारा, इसलिए आपको सभी प्रविष्टियां ओ (एन) निकालना होगा और उन्हें ओ (एनएलओएनएन) सॉर्ट करना होगा जबकि आप ओ में प्राकृतिक क्रम में बाइनरी सर्च पेड़ को पार कर सकते हैं (एन)।
ध्यान दें कि जावा में, उदाहरण के लिए, एक लिंक्ड हैशसेट और लिंक्ड हैशैप है जो आपको हैश के कुछ फायदे देता है लेकिन जिसे इसे जोड़ा गया क्रम में पार किया जा सकता है, ताकि आप इसे सॉर्ट कर सकें और सक्षम हो सकें उस क्रमबद्ध क्रम में इसके साथ-साथ हैश द्वारा वस्तुओं को निकालने के लिए इसे पार करें।
सही, एक हैश तालिका आपको जिस तरह से संभवतः "क्रमबद्ध" नहीं है। हैश टेबल में तत्व पूरी तरह से हल नहीं होते हैं, आमतौर पर, हालांकि व्यवस्था अक्सर एक तरह के पड़ोस में होती है। लेकिन उन्हें हैश फ़ंक्शन के अनुसार व्यवस्थित किया जाता है, जो आमतौर पर समान वाक्यांशों के लिए जंगली रूप से भिन्न होता है। यह मानव द्वारा उपयोग की जाने वाली किसी मीट्रिक द्वारा एक तरह का नहीं है।
यदि आपके संग्रह के साथ आप जो मुख्य चीज कर रहे हैं वह क्रमबद्ध क्रम में प्रिंट कर रहा है, तो आप किसी प्रकार के बीएसटी का उपयोग कर सबसे अच्छे हैं।
एक बाइनरी सर्च पेड़ इस तरह से संग्रहीत किया जाता है कि यदि आप पहली बार गहराई से ट्रैवर्सल करते हैं, तो आपको क्रमबद्ध क्रम में आइटम मिलेंगे (माना जाता है कि आपके पास लगातार तुलना फ़ंक्शन है)। वृक्ष में पहले से ही लौटने वाले सामानों का बिग ओ पेड़ को पार करने का बिग ओ होगा।
आप हैश टेबल के बारे में सही हैं, वे क्रमबद्ध नहीं हैं। वास्तव में, एक सादा हैश टेबल में सब कुछ गिनने के लिए, आपको यह देखने के लिए हर बाल्टी को देखना होगा कि वहां क्या है, इसे खींचें, फिर आपको जो मिलता है उसे सॉर्ट करें। उसमें से एक क्रमबद्ध सूची प्राप्त करने के लिए बहुत सारे काम।
सही है, एक हैश तालिका में संग्रहीत सॉर्ट किए गए डेटा को धीमा कर दिया जाएगा क्योंकि हैश तालिका डेटा को सॉर्ट नहीं किया गया है। यह आपको एक विशेष आइटम खोजने का एक त्वरित तरीका देता है। "Big O Notation" में कहा जाता है कि आइटम निरंतर समय में पाया जा सकता है, यानी ओ (1) समय।
दूसरी तरफ, आप "लॉगरिदमिक टाइम" (ओ (लॉग एन) में बाइनरी सर्च पेड़ में एक आइटम पा सकते हैं क्योंकि डेटा पहले से ही आपके लिए सॉर्ट किया गया है।
तो यदि आप एक क्रमबद्ध सूची मुद्रित करना चाहते हैं, तो आप सॉर्ट किए गए क्रम में संग्रहीत डेटा (यानी एक बाइनरी पेड़) से बहुत बेहतर हैं।
, का आनंद लें
रॉबर्ट सी Cartaino
यह दिलचस्प सवाल के एक जोड़े को लाता है। क्या एक खोज पेड़ अभी भी निम्नलिखित पर विचार कर रहा है?
इसके अलावा छोड़ें सूची से संबंधित विचारों की जाँच बनाम बाइनरी ट्री: Skip List vs. Binary Tree