जावा में ट्रीसेट ऑपरेशंस की कम्प्यूटेशनल जटिलता?

Question

मैं ट्रीसेट के कुछ संचालन में जटिलता के बारे में कुछ चीजों को साफ़ करने की कोशिश कर रहा हूं। जावाडोक पर यह कहते हैं:

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

अब तक इतना अच्छा है। मेरा प्रश्न addAll(), removeAll() आदि पर क्या होता है समूह के लिए यहां जावाडोक कहते है:

"अगर निर्दिष्ट संग्रह भी एक सेट है, addAll आपरेशन प्रभावी ढंग से ताकि इस सेट को संशोधित करता है इसके मान दो सेटों का संघ है। "

क्या यह सिर्फ ऑपरेशन के तार्किक परिणाम को समझा रहा है या क्या यह जटिलता के बारे में संकेत दे रहा है? मेरा मतलब है, अगर दो सेटों का प्रतिनिधित्व किया जाता है उदा। लाल-काले पेड़ों को किसी एक के दूसरे तत्व को "जोड़ने" की तुलना में किसी भी तरह पेड़ में शामिल होना बेहतर होगा।

किसी भी मामले में, क्या दो ट्रीसेट्स को ओ (लॉगन) जटिलता के साथ एक साथ जोड़ने का कोई तरीका है?

अग्रिम धन्यवाद। :-)

Answer 1

आप कल्पना कर सकता है कि यह कैसे O(log n) को विशेष मामलों अनुकूलन करने के लिए संभव हो जाएगा, लेकिन सबसे ज्यादा मामले होने के लिए जहां m और n हर एक पेड़ में तत्वों की संख्या रहे हैं मिल गया है।

संपादित करें: S1 के सभी सदस्यों S2 के सभी सदस्यों से कम होना चाहिए:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

एक विशेष मामले के एल्गोरिथ्म कि O(log(m + n)) में पेड़ शामिल हो सकें लेकिन प्रतिबंध नोट कर सकते हैं वर्णन करता है। मेरा यही मतलब है कि विशेष मामलों के लिए विशेष अनुकूलन हैं।

Answer 2

इस ब्लॉग पोस्ट के अनुसार:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
यह हे है (एन एन लॉग इन करें)। चूंकि दस्तावेज़ीकरण जटिलता के बारे में कोई संकेत नहीं देता है, इसलिए यदि आपके लिए प्रदर्शन महत्वपूर्ण है तो आप अपना स्वयं का एल्गोरिदम लिखना चाहेंगे।

Answer 3

ट्रीसेट के लिए जावा स्रोत को देखते हुए, ऐसा लगता है कि पारित संग्रह एक सॉर्टेडसेट है, तो यह ओ (एन) समय एल्गोरिदम का उपयोग करता है। अन्यथा यह super.addAll को कॉल करता है, जिसे मैं अनुमान लगा रहा हूं परिणामस्वरूप ओ (एन लॉगन) होगा।

संपादित करें - लगता है कि मैं कोड बहुत तेजी से पढ़ते हैं, TreeSet केवल हे (एन) कलन विधि का उपयोग कर सकते हैं अगर यह समर्थन है नक्शा खाली है

Answer 4

यह पेड़ के विलय करते हैं या Disjoint- में की तरह सेट में शामिल होने के लिए संभव नहीं है डेटा संरचनाएं सेट करें क्योंकि आप नहीं जानते कि 2 पेड़ के तत्व अलग हैं या नहीं। चूंकि डेटा संरचनाओं के पास अन्य पेड़ों में सामग्री के बारे में ज्ञान है, इसलिए यह जांचना आवश्यक है कि इसमें कोई तत्व अन्य पेड़ में जोड़ने से पहले या कम से कम इसे किसी अन्य पेड़ में जोड़ने की कोशिश कर रहा है और यदि आप इसे पाते हैं तो इसे जोड़ना बंद कर दें रास्ता। तो, यह ओ (एमएलएलएन)