दो std::set एस दिए गए, कोई भी दोनों सेटों के साथ-साथ एक साथ फिर से सक्रिय हो सकता है और तत्वों की तुलना कर सकता है, जिसके परिणामस्वरूप रैखिक जटिलता हो सकती है। यह std::unordered_set एस के लिए काम नहीं करता है, क्योंकि तत्व किसी भी क्रम में संग्रहीत किए जा सकते हैं। तो std::unordered_set के लिए a == b कितना महंगा है?समानता के लिए दो असाधारण सेट की तुलना कितनी महंगा है?
operator== और operator!= की जटिलता:
रैखिक जटिलता। एन सबसे खराब मामले में, जहां एन कंटेनर का आकार है। मानक §23.2.5 में
अधिक जानकारी, बिंदु 11:
unordered_set के लिए और unordered_map, की जटिलता operator== (यानी, value_type की == ऑपरेटर के लिए कॉल की संख्या, विधेय द्वारा वापस करने के लिए key_equal(), और hasher hash_function() द्वारा दिया) के लिए सबसे खराब स्थिति है, जहां Na.size() है में औसत के मामले में और एन को 2N लिए आनुपातिक है।
ओ (एन²) का सबसे बुरा मामला है।
लेकिन असंगत सेट वास्तव में हैश द्वारा आदेश दिया गया है। तो हैश की तुलना करना संभव है (यदि यह सेट विफल हो जाता है तो बराबर नहीं हो सकता है) और उसके बाद सत्यापित करें कि उसी हैश (रैखिक) के पास एक ही हैश के साथ अलग-अलग मानों के लिए वास्तविक मूल्य (ओ (एन²) है।
सबसे अच्छे मामले में यह ओ (एन) है।
आम तौर पर जटिलता ओ (एन) होती है यदि हैश फ़ंक्शन "अच्छा" (अलग-अलग ऑब्जेक्ट्स -> हमेशा अलग हैश) और ओ (एन²) है यदि हैश फ़ंक्शन "खराब" है (सबकुछ हमेशा एक जैसा होता है हैश मान)
"हैश फ़ंक्शन अच्छा है (अलग-अलग ऑब्जेक्ट्स -> हमेशा अलग हैश)" -> एक भयानक हैश एल्गोरिदम के लिए अलग-अलग हैंश भी सच हो सकते हैं (उदाहरण के लिए 8 * 128-बिट हैश मान लौटाकर 128 वर्ण तक हैश स्ट्रिंग्स स्ट्रिंग), लेकिन बाल्टी की संख्या में संशोधन और परिणाम बदसूरत है। जब टक्कर से बचने में मदद करने वाले इनपुट में कोई विशेष अंतर्दृष्टि नहीं होती है, तो एक अच्छा हैश फ़ंक्शन पोस्ट मोडिंग आमतौर पर अप्रयुक्त बाल्टी के अनुपात में टकराव होता है ... जो अभी भी ओ (एन) औसत में परिणाम देता है। –
@ टोनीडेलॉय: इसे इंगित करने के लिए धन्यवाद! एक "अच्छा हैश" न केवल "अलग-अलग मूल्यों" को वापस लौटाएगा, बल्कि बाल्टीओं को "अच्छी तरह से वितरित" सम्मान भी देना चाहिए (हैश स्पेस बाल्टी के समान और प्रमुख सम्मान होना चाहिए, केवल आपके द्वारा उल्लेख किए गए प्रभाव को कम करने के लिए) –
क्या आपके पास सेट सदस्यता की जांच करने का एक प्रभावी तरीका है (उदाहरण के लिए वे हैशटेबल्स द्वारा समर्थित हैं)? – Thilo
सी ++ मानक के शब्दों को समझने और समझने में स्पष्ट, सीधा, आसान: "दो unordered कंटेनर' ए' और 'बी' बराबर तुलना करें यदि' a.size() == b.size() 'और प्रत्येक के लिए 'a.equal_range (Ea1)' से प्राप्त समकक्ष-कुंजी समूह '[Ea1, Ea2)' 'b.equal_range (Ea1) 'से प्राप्त समकक्ष-कुंजी समूह' [Eb1, Eb2)' मौजूद है, जैसे कि ' दूरी (ईए 1, ईए 2) == दूरी (ईबी 1, ईबी 2) 'और' is_permutation (ईए 1, ईए 2, ईबी 1) '' सत्य 'देता है। 'unordered_set' के लिए ...' ऑपरेटर == 'की जटिलता ... है औसत मामले में 'एन' के अनुपात और सबसे खराब मामले में' N^2' के लिए आनुपातिक, जहां 'एन'' a.size() 'है। –