C++词频统计场景下键值后续排序的最优复杂度问询

现有方案复杂度分析 #

• 统计阶段：使用std::map做频次统计，单次插入时间复杂度为O(log M)（M为唯一单词总数），总单词数为N的情况下，整体统计复杂度为O(N log M)
• TopK筛选阶段：使用小顶堆遍历筛选，单次堆操作复杂度为O(log K)（K为需要返回的Top元素数量，默认10），整体筛选复杂度为O(M log K)

可优化的实现方案 #

1. 统计阶段优化：替换std::map为std::unordered_map #

std::map底层是红黑树，插入时需要维护有序性带来额外开销。替换为哈希表实现的std::unordered_map后，单次插入平均复杂度降为O(1)，统计阶段整体平均复杂度降到O(N)，实际运行效率会有非常明显的提升，是最直接的复杂度优化点。

2. TopK筛选阶段分场景选最优方案 #

场景1：K值较小（如默认的10、几十以内）

你当前使用的小顶堆方案已经是最优的，O(M log K)的复杂度远低于全量排序的O(M log M)，无需调整。

场景2：K值较大（接近M或者到几千以上的规模）

可以改用桶排序方案，时间复杂度可以降到线性：

1. 统计完所有单词频次后，先找到最高频次值max_freq，创建大小为max_freq + 1的桶数组，每个桶存储对应频次的所有单词
2. 从最高频次的桶开始倒序遍历，依次取出单词直到凑够K个即可
3. 该阶段整体复杂度为O(M + max_freq)，只要单词最高频次不是极端大的情况，效率远高于堆方案

简化代码示例（unordered_map + 小顶堆实现） #

#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;

int main(int argc, char* argv[]) {
    int top_k = 10;
    if (argc > 1) top_k = stoi(argv[1]); // 支持自定义K值

    unordered_map<string, int> freq_map;
    ifstream fin("input.txt");
    string word;
    while (fin >> word) {
        // 可在此处添加单词归一化逻辑：转小写、去标点等
        freq_map[word]++;
    }

    // 小顶堆：pair<频次, 单词>
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
    for (auto& p : freq_map) {
        if (pq.size() < top_k) {
            pq.push({p.second, p.first});
        } else if (p.second > pq.top().first) {
            pq.pop();
            pq.push({p.second, p.first});
        }
    }

    // 输出结果
    while (!pq.empty()) {
        cout << pq.top().second << ": " << pq.top().first << endl;
        pq.pop();
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者p3t3