ट्रीसेट में आदेशित संचालन की समय जटिलता क्या है?

Question

java.util.TreeSet में निम्न परिचालनों की समय जटिलता क्या है?

• first()
• last()
• lower()
• higher()

मुझे लगता है कि इन लगातार समय कर रहे हैं लेकिन एपीआई कोई गारंटी नहीं देता।

Answer 1

असल में, मैंने सोचा होगा कि उन परिचालनों को सामान्य कार्यान्वयन के लिए O(logN) होने जा रहे हैं।

• first() के लिए और last()O(1) TreeSet कार्यान्वयन क्रमशः पेड़ में वाम-पंथी और दायीं ओर का पत्र-गांठ करने के लिए एक सूचक बनाए रखने के लिए की आवश्यकता होगी किया जाना है। इन्हें बनाए रखना हर प्रविष्टि के लिए निरंतर लागत जोड़ता है और कम से कम प्रत्येक हटाने के लिए निरंतर लागत जोड़ता है। हकीकत में, कार्यान्वयन शायद फ्लाई पर बाएं/दाएं नोड्स पाएंगे ... जो O(logN) ऑपरेशन है।

• lower() और higher() तरीकों get रूप में एक ही काम करने के लिए है और इसलिए O(logN) हैं।

बेशक, आप वास्तव में क्या होता है यह देखने के लिए स्रोत कोड को स्वयं देख सकते हैं।

Answer 2

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

प्रलेखन से:

इस कार्यान्वयन (जोड़ने, हटाने और शामिल हैं) गारंटी लॉग (एन) बुनियादी कार्यों के लिए समय लागत प्रदान करता है।

ये आपके द्वारा किए गए कार्यों नहीं हैं, लेकिन इस बारे में सोचें कि जावा ट्रीसेट को कैसे पार करेगा।

Answer 3

यह कार्यान्वयन पर निर्भर करेगा। मैं जावा से अविश्वसनीय रूप से परिचित नहीं हूं, लेकिन ऐसा लगता है कि उन सभी परिचालनों में ट्रैवर्सल ऑपरेशंस हैं (निम्नतम तत्व प्राप्त करें, उच्चतम तत्व प्राप्त करें, अगले उच्च या अगले निचले स्तर पर जाएं)।

ट्री एक AVL Tree, या एक संतुलित-वृक्ष संरचना के किसी भी अन्य प्रकार की तरह एक Self-Balancing Binary Search Tree के रूप में कार्यान्वित किया जाता है, तो आप प्रत्येक के लिए औसत-प्रकरण और बुरी से बुरी हालत हे (लॉग एन) पर विचार करना करने के लिए समय जा रहे हैं संचालन के, और ओ (1) का सबसे अच्छा मामला।

Answer 4

दोनों पहले की तरह लग रहा() और पिछले() हे (लॉग एन) और नहीं हे हो जाएगा (1) ट्री-मैप की Implentation (सूरज JDK 1.6.0_23) जो डिफ़ॉल्ट रूप से TreeSet द्वारा प्रयोग किया जाता है के आधार पर:

/** 
* Returns the first Entry in the TreeMap (according to the TreeMap's 
* key-sort function). Returns null if the TreeMap is empty. 
*/ 
final Entry<K,V> getFirstEntry() { 
    Entry<K,V> p = root; 
    if (p != null) 
     while (p.left != null) 
      p = p.left; 
    return p; 
} 

/** 
* Returns the last Entry in the TreeMap (according to the TreeMap's 
* key-sort function). Returns null if the TreeMap is empty. 
*/ 
final Entry<K,V> getLastEntry() { 
    Entry<K,V> p = root; 
    if (p != null) 
     while (p.right != null) 
      p = p.right; 
    return p; 
} 

Answer 5

मैंने वास्तव में http://developer.classpath.org/doc/java/util/TreeSet-source.html में स्रोत कोड, देखा, पहले() मानचित्रों को कॉल करता है।firstKey() तो http://developer.classpath.org/doc/java/util/TreeMap-source.html

393: public K firstKey() 
394: (
395: if (root == nil) 
396: throw new NoSuchElementException(); 
397: return firstNode().key; 
398:) 

और firstNode() में में, यह है, जबकि पाश छोड़ दिया

952: final Node<K, V> firstNode() 
953: (
954: // Exploit fact that nil.left == nil. 
955: Node node = root; 
956: while (node.left != nil) 
957: node = node.left; 
958: return node; 
959:)