c++ - 搜索使用对应值稍后用于排序的键时的最佳复杂度

编辑：要显示的元素数量可以是用户定义的，默认为 10，但可以定义为一个非常大的数字。

我有一个解析单词的文件，然后我需要计算每个单词在文本中出现的次数，并显示出现次数最多的 10 个单词（使用 C++）。

我目前将每个解析的单词插入到 std::map 中，单词是键，它的出现次数是值。每次遇到不属于 std::map 的单词时，我都会将其添加为初始值 1，每次遇到属于 map 的单词时，我将其当前值加 1。

解析完文件后，我有一个包含文本中所有唯一单词及其出现次数的映射，但该映射未按键的值排序。

此时我可以遍历 std::map 并将其单词推入优先级队列（以最小值排序），一旦优先级队列达到 10 个单词的最大容量，我检查我要插入的值是否更大然后是顶部的值，如果是，我弹出顶部并插入值（如果不是，我从 std::map 转到下一个值。

因为每个单词只出现一次（在这个阶段），我确定优先级队列中的每个值都是唯一的。

我的问题是，这可以更有效地解决共谋问题吗？

标签： c++data-structurestime-complexity

这是 python 的 collections.Counter，所以你可以在那里寻找一个真实的例子。它本质上与您正在做的事情相同：通过增加字典来获取计数，然后在 (word, count) 对上使用 heapq.nlargest。（优先队列是一个堆。我不知道他们为什么要添加一个 Q。）

考虑从 N 个单词中选择 m 个最大/最小的单词。这应该有一个 O(N log m) 的理论极限

您应该使用 std::unordered_map 在 O(N) 时间内创建计数。这很重要，你不关心按字母顺序对单词进行排序，所以不要在这里使用 std::map 。如果你使用 std::map，你已经在 O(N log N) 这大于理论限制。

现在，在选择前 10 项时，您几乎需要任何一次只查看 10 项的方法。具有最大大小的优先级队列是一个不错的选择。重要的一点是，您不会跟踪超出您需要的范围。您在这里的复杂性是 O(N log m)，在 n 与 N 相比较小的特殊情况下变为 O(N)。但常见的错误是在比较项目时包括整个数据集。

但是，请检查 m >= N，因为如果您确实需要整个数据集，您可以调用 std::sort。我假设你需要它们。如果你不这样做，这个案子就会变得非常琐碎。并检查 m==1 这样你就可以使用 max。

总之，除了使用了错误的地图，我相信你已经达到了大 O 复杂度的理论极限。