对于 C++ STL 容器，例如vector and list，查找元素并插入或删除它们的复杂性是不言而喻的。然而，对于map容器，尽管我从阅读中知道访问和插入复杂性/性能是 O(log(n))，但我无法计算出why。我显然对地图的理解不够深入，因此非常感谢有关此主题的一些启发。
映射或集合的元素包含在树结构中；每次检查树的节点时，您都会确定要查找/插入的元素是否小于或大于该节点。您需要执行此操作的次数（对于正确平衡的树）是 log2(N)，因为每次比较都会抛出一半的可能性。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
