std :: map的时间复杂度是多少 [英] What is the time complexity of std::map

问题描述

std :: map的时间复杂度是多少? 在最坏的情况下会退化吗? 还是由实现决定，我们不知道吗?

What is the time complexity of std::map? And will it degenerate in the worst case? Or it is decide by the implementation, we can't know it?

推荐答案

查阅与log(N)成正比.在典型情况下(以红黑树的形式实现)，比较次数最多可以达到Log ₂ N的两倍.

Lookups are proportional to log(N). In a typical case (implementation as a red-black tree) the number of comparisons can be up to twice Log₂N.

插入通常与Log ₂ N成正比 ，但是当您插入许多已经按顺序排列的项目时，有一项特殊规定 ¹ .在这种情况下，您可以为插入位置指定提示".当该提示正确时，每个插入都是(摊销)O(1)而不是O(Log N)，因此按排序顺序插入一系列项是线性的，而不是N log(N).您指定的提示是要插入的项目之后位置的迭代器.

Insertions are normally proportional to Log₂N as well--but there's a special provision made for when you're inserting a number of items that are already in order¹. In this case, you can specify a "hint" for where an insertion is going to take place. When that hint is correct, each insertion is (amortized) O(1) instead of O(Log N), so inserting a range of items in sorted order is linear instead of N log(N). The hint you specify is an iterator to the position just after the item to be inserted.

例如，如果文件中有许多项目按排序顺序，并且要将它们插入到地图中，则可以将your_map.end()指定为提示"，并且构建地图将具有O( N)个复杂度，而不是O(N Log N)个复杂度.

For example, if you have a number of items in a file in sorted order, and you want to insert them into the map, you can specify your_map.end() as the "hint", and building the map will have O(N) complexity instead of O(N Log N) complexity.

_{1.从技术上讲，这适用于您插入项目的任何时候，不仅是在按顺序插入项目时，而且到目前为止，最常见的情况是您有合理的提示"可用时是在按顺序插入项目时.}

_{1. Technically, this applies anytime you insert items, not just when you're inserting them in order--but by far the most common case where you have a reasonable "hint" available is when you're inserting items in order.}

这篇关于std :: map的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！