std :: map class पर find() फ़ंक्शन कितना कुशल है? क्या यह कुंजी की तलाश में सभी तत्वों के माध्यम से पुनरावृत्त करता है जैसे कि यह ओ (एन) है, या यह एक संतुलित पेड़ में है, या क्या यह हैश फ़ंक्शन का उपयोग करता है या क्या?std :: map में find() की समय जटिलता?
Log(n) यह लाल काले पेड़ पर आधारित है।
संपादित करें: एन निश्चित रूप से मानचित्र में सदस्यों की संख्या है।
हालांकि यह एक हद तक सच है, बड़े नक्शे में एक सीमा है। यदि आप बहुत बड़े डेटासेट देख रहे हैं तो मैं वैकल्पिक सहयोगी सरणी कंटेनरों को भी देखने की सलाह दूंगा। –
सच है यह लॉग है (एन)। सच नहीं है यह लाल/काले पेड़ों पर आधारित है। मानक ऑपरेशन को लॉग (एन) की अधिकतम जटिलता के लिए परिभाषित करता है और इसे प्राप्त करने का सबसे प्रभावशाली तरीका लाल/काले पेड़ों का उपयोग करना है (हालांकि यह एक आवश्यकता नहीं है)। इस प्रकार घोड़े से पहले आपका गाड़ी है। –
@OrgnlDave: यह हमेशा सच है (कुछ हद तक नहीं)। –
यह सभी तत्वों को पुन: सक्रिय नहीं करता है, यह एक बाइनरी खोज करता है (जो ओ (लॉग (एन)) है। यह ऑपरेटर < या खोज करने के लिए एक तुलनित्र का उपयोग करें।
यदि आप हैश नक्शा चाहते हैं, तो आप एक std :: unordered_map (सी ++ - 0x पर जोड़ा गया) का उपयोग कर सकते हैं, जो हैश फ़ंक्शन और औसत पर (हैश फ़ंक्शन और आपके द्वारा प्रदान किए जाने वाले डेटा के आधार पर) का उपयोग कर सकता है() ओ (1) हो।
@ निकोलबोलस: मुझे कहीं पढ़ना याद है कि यह एक बाएं पेड़ अनिवार्य नहीं था, आपकी टिप्पणी के लिए धन्यवाद। मेरे एवर फिक्स्ड। – fbafelipe
std::map और std::set अत्यधिक संतुलित बाइनरी खोज पेड़ों (जैसे लाल-काले पेड़, एवीएल पेड़) का उपयोग करके कंपाइलर विक्रेताओं द्वारा कार्यान्वित किया जाता है।
जैसा कि डेविड द्वारा सही ढंग से इंगित किया गया है, find ओ (लॉग एन) समय लेगा, जहां एन कंटेनर में तत्वों की संख्या है।
लेकिन उस int, long, char, double आदि जैसे आदिम डेटा प्रकार, तार के साथ नहीं के साथ है।
तो std:string देता आकार 'm' का कहना है कि, संतुलित द्विआधारी खोज वृक्ष की ऊंचाई traversing लॉग n तुलना पेड़ की एक प्रवेश के साथ दिया कुंजी के की आवश्यकता होगी, कुंजी के रूप में प्रयोग किया जाता है।
जब std::stringstd::map या std::set, find और insert संचालन के प्रमुख हे (एम लॉग एन), जहां मीटर दिए गए स्ट्रिंग की लंबाई पाया जा करने की जरूरत है खर्च होंगे है।
मैं यह इंगित करने के लिए इसे ऊपर उठाने जा रहा था कि व्यक्तिगत तुलना अनिवार्य रूप से ओ (1) नहीं है। लेकिन फिर आपने जावा के बारे में संपादन किया, जिसे मैं समझ नहीं पा रहा हूं। 'हैशकोड()' द्वारा लौटाई गई हैश कुंजी एक अद्वितीय पहचानकर्ता नहीं है, इसलिए जब भी आप दो कुंजियों की तुलना करते हैं तो आपको अभी भी ओ (एम) स्ट्रिंग तुलना करने की आवश्यकता होती है। – jogojapan
इसके अलावा, हैशकोड उत्पन्न करना अभी भी ओ (एम) है, इसलिए न केवल यह तेज़ नहीं है, हैशकोड का उपयोग करके _slower_ होगा (माना जाता है कि वे कैश नहीं हैं) –
@jogojapan java.lang.String.hashCode को इंगित करने के लिए धन्यवाद () चीज, जावज हिस्से को हटाकर और पूछे जाने वाले सवाल पर चिपके हुए मेरे जवाब को सही किया। एक [प्रश्न] भी उठाया (http://stackoverflow.com/questions/17569651/are-string-hashcode-in-java-pre-computed) –
एसटीएल के लिए दस्तावेज है, और यह आमतौर पर जटिलता बताता है। http://www.cplusplus.com/reference/stl/map/find/ –
देखें: [मानक कंटेनरों की जटिलता गारंटी क्या हैं] (http://stackoverflow.com/q/181693/14065) –