http://www.cplusplus.com/reference/unordered_set/unordered_set/find/

एक unordered_set में खोजने की समय जटिलता एक unordered_set के लिए औसतन स्थिर रहने के लिए दी गई है। यदि मेरे पास स्ट्रिंग्स का एक unordered_set है, तो उस सेट में एक स्ट्रिंग खोजने की समय जटिलता क्या होगी? क्या यह स्थिर होगा या ओ (स्ट्रिंग की लंबाई)?

2
Learner 18 अप्रैल 2020, 07:48

1 उत्तर

सबसे बढ़िया उत्तर

std::unordered_set को हैश टेबल के रूप में लागू किया गया है। इसकी find विधि में O(1) की औसत-केस जटिलता और [tab:container.hash.req]


डिफ़ॉल्ट रूप से, std::unordered_set<std::string> कुंजियों की तुलना करने के लिए operator== का उपयोग करता है, इसलिए प्रत्येक कुंजी तुलना O(str.size()) में चलती है जैसा कि [string.view.ops] (operator==(const std::string&, const std::string&) को std::string_view(str1) == std::string_view(str2) के बराबर परिभाषित किया गया है, जिसे परिभाषित किया गया है std::string_view(str1).compare(std::string_view(str2) == 0 के बराबर)।

std::unordered_set<std::string> के लिए, कंटेनर को खोजने के लिए स्ट्रिंग के हैश की गणना करनी चाहिए। डिफ़ॉल्ट रूप से यह इसके लिए std::hash<std::string> का उपयोग करता है। मानक std::hash<std::string> के लिए कोई जटिलता आवश्यकताओं को निर्दिष्ट नहीं करता है, लेकिन इसकी सबसे अधिक संभावना O(str.size()) है।

1
Miles Budnek 18 अप्रैल 2020, 05:45