ste*_*t99 32 c++ std data-structures c++11
关键是在std::mapO(1)上查找？我以为直到我想到它为止.它基于树实现,因此查找时间应为O(log N),对吗？
而且,是否有可能让O(1)查找字符串键std::unordered_map？
And*_*owl 46
查找的复杂性std::map是O(log N)(容器大小的对数).
根据C++ 11标准的第23.4.4.3/4段std::map::operator []:
复杂性:对数.
查找的复杂性std::unordered_map在平均情况下是O(1)(常数),在最坏情况下是O(N)(线性).
根据C++ 11标准的第23.5.4.3/4段 std::unordered_map::operator []
复杂性:平均情况O(1),最坏情况O(
size()).
注意:
如果您的问题仅涉及计算复杂性,那么上面写的内容应该回答它.事实上,操作的计算复杂性是根据容器的大小(它包含的元素的数量)来衡量的.
但是,如果您正在寻找一种在使用字符串键的容器上执行O(1)查找的方法,并且查找的复杂性相对于字符串的长度而不是容器的大小是恒定的,那么答案就是std::unordered_map不符合你的要求.
为了查找密钥,首先需要产生它的哈希值; 当键是一个字符串时,这个操作本身可以是字符串大小的线性.然后,实现必须将密钥与同一存储桶中的所有字符串密钥进行比较,并且这些比较中的每一个在这些字符串的大小上依次是线性的.
是的,确实std::map 会有O(log N)并且std::unordered_map将具有平均恒定时间复杂度,并且O(N)在最坏的情况下,如果存在太多的哈希冲突.
| 归档时间： |
|
| 查看次数： |
33906 次 |
| 最近记录： |