对于 vector
和 list
等 C++ STL 容器,查找元素并插入或删除它们的复杂性是不言自明的。然而,对于 map
容器,尽管我从阅读中知道访问和插入复杂度/性能是 O(log(n)),但我无法弄清楚为什么。显然,我对 map 的理解程度还不够,因此非常感谢对这个主题的一些启发。
最佳答案
映射或集合的元素包含在树结构中;每次检查树的节点时,您都会确定要查找/插入的元素是小于还是大于该节点。您需要执行此操作的次数(对于适当平衡的树)是 log2(N),因为每次比较都会排除一半的可能性。
关于c++ - 为什么C++ STL map容器的复杂度是O(log(n))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11234921/