जावा में सेट की समय जटिलता

Question

क्या कोई मुझे नीचे दिए गए कोड की समय जटिलता बता सकता है?

a int की एक सरणी है।

Set<Integer> set = new HashSet<Integer>(); 
for (int i = 0; i < a.length; i++) { 
    if (set.contains(arr[i])) { 
     System.out.println("Hello"); 
    } 
    set.add(arr[i]); 
} 

मुझे लगता है कि यह है हे (एन), लेकिन मुझे यकीन है कि क्योंकि यह Set उपयोग कर रहा है नहीं कर रहा हूँ और इस तरीके के रूप में अच्छी तरह से शामिल हैं। यह set की add विधि को भी कॉल कर रहा है।

क्या कोई भी पुष्टि कर सकता है और समझा सकता है कि पूरे उपरोक्त कोड की समय जटिलता क्या है? इसके अलावा, यह कितना स्थान लेगा?

Answer 1

मैं सरणी पर विश्वास है कि इसका हे (एन) क्योंकि आप पाश, और contains और add निरंतर समय होना चाहिए, क्योंकि इसके एक हैश आधारित सेट। यदि यह हैश आधारित नहीं था और लुकअप करने के लिए पूरे सेट पर पुनरावृत्ति की आवश्यकता होती है, तो ऊपरी बाउंड एन^2 होगी।

इंटीग्रर्स अपरिवर्तनीय हैं, इसलिए अंतरिक्ष जटिलता 2 एन होगी, जो मुझे विश्वास है कि केवल एन को सरल बनाता है, क्योंकि स्थिरांक कोई फर्क नहीं पड़ता।

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

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

here देखें।