c++ - 这个给定数据结构的时间复杂度

Question

我才刚刚开始了解时间复杂度，我只是想确保我做对了。

如果我们有一个 unordered_map<string, set<int>>

请注意，组织为哈希表，不允许负载因子超过某个常量。

假设字符串是企业名称，在 set<int> 中我们有员工 ID，如果我们想打印某个给定业务中的所有员工 ID，时间复杂度是多少。这是我的逻辑，如果我的方向正确，请告诉我。

我的逻辑是这样的，因为哈希表加载常数不会超过某个常数，所以找到一个特定的业务将是常数时间操作所以O(1)。打印列表中的所有名称基本上是顺序遍历的 BST，因此平均为 O(N)。因此总体上它将是 O(1)+O(N)，基本上是 O(N)。这是正确的吗？

Answer 1

嗯，重要的是要了解您如何计算复杂性。

假设您在第一个容器和 std::set<int> 中有 N 个条目包含 M 个元素。使用允许快速搜索的容器，第一部分是 O(1)，然后打印是 O(M)。

但是，如果您使用类似 std::vector 的东西复杂度为 O(N)+O(M)(因为搜索速度很慢)。对于常规映射，它将是 O(logN)+O(M)。

由于 N 和 M(没有更多数据)不相关，您不能将它们放在 O 表达式中。