c++ - 将 N 项插入空 std::map 的复杂性

Question

我想知道以下功能的复杂性。
我知道 std::map 被实现为红黑树，插入的复杂度为 O(logN)。
但是，如果我继续向空地图添加 N 个项目，我该如何计算呢？

void add(int N, std::map<int, int>& map) {
  for (int i = 0; i < N; ++i) {
    map[i] = i;
  }
}

提前致谢，

score 2 · Accepted Answer

2

你做了 N 次 O(log N) 的事情，所以它是 O(N log N)。

于 2013-03-20T03:45:34.147 回答

score 2 · Accepted Answer

RB树是一种平衡二叉树。插入操作基本上是找到插入位置，为新插入的节点分配空间并调整指针，然后重新平衡 RB 树。插入的复杂度是 O(logN)。

因为在您的情况下，您首先确定某些操作的复杂性，即具有 log(N) 复杂性的插入，然后找出该操作使用了多少次。这就是我们有 N(logN) 的原因。O(logN) 表示容器中元素数量所用时间的增长顺序最多为 logN 的顺序。这并不意味着实际使用的时间是 logN。

如果您的应用程序是时间批评者，您可以考虑使用，unordered_map因为插入时间复杂度是恒定的。您正在从 int 映射到 int，因此在这种情况下使用 unordered_map 应该非常好。

BTW：在你的公式中，log0 没有定义，当没有要插入的元素时，你不进行插入操作。

score 2 · Accepted Answer

你在问一个合理的问题。

将 N 项插入一棵一开始为空的树时，您将从 log(0) 开始并前进到 log(N)。这意味着您的总体平均水平实际上log(N/2)是log(N).

在对数的情况下，这并没有真正的区别——整体复杂性仍然是对数的。你所做的实际上改变了对数的底数。

3 回答 3