如何降低图顶点最大权重统计代码的时间复杂度？

原代码功能与性能瓶颈 #

你的代码用于遍历图的顶点，对比每个顶点及其邻居的权重找出最大值，并记录每个顶点被标记为最大值的次数（存在X中）。但目前实现里多次调用map::find，而map是基于红黑树的有序容器，每次find都是O(log n)时间复杂度，重复调用会显著拉低性能，主要的冗余点就是你列出的三处重复查找操作。

具体优化方案 #

1. 减少重复查找操作

原代码中对同一个键多次调用find，完全可以缓存查找结果，避免重复计算：

void find_max_w()
{
    double max_w = 0.;
    double idx_max; // 修正原代码类型不匹配问题：用double存double类型的顶点ID，避免精度丢失
    for (const auto &pair : adjacency)
    {
        max_w = 0;
        // 缓存当前顶点的权重，只执行一次查找
        auto w_it = W.find(pair.first);
        double current_weight = w_it->second;
        if (current_weight > max_w) {
            max_w = current_weight;
            idx_max = pair.first;
        }
        // 遍历邻居时同样缓存权重，避免重复查找
        for (double d : pair.second)
        {
            auto neighbor_w_it = W.find(d);
            double neighbor_weight = neighbor_w_it->second;
            if (neighbor_weight > max_w) {
                max_w = neighbor_weight;
                idx_max = d;
            }
        }
        // 缓存X的迭代器，减少一次查找操作
        auto x_it = X.find(idx_max);
        x_it->second += 1;
    }
}

2. 替换更高效的数据结构

如果不需要map的有序特性，完全可以用**哈希表（unordered_map）**替代，它的平均查找时间复杂度是O(1)，远优于map的O(log n)：

// 将所有map替换为unordered_map
unordered_map<double, list<double>> adjacency;
unordered_map<double, double> degree;
unordered_map<double, double> W;
unordered_map<double, double> X;

如果你的顶点ID可以映射为连续的整数（比如把double类型的ID转换为0~n-1的索引），**vector**是最优选择——直接通过索引访问，时间复杂度O(1)，性能比哈希表还要好：

// 假设顶点ID已映射为0到n-1的整数
vector<vector<int>> adjacency; // 邻接表，存储顶点索引
vector<double> W; // 权重数组，W[i]对应顶点i的权重
vector<int> X; // 计数数组，X[i]对应顶点i被标记的次数

void find_max_w() {
    int n = adjacency.size();
    X.assign(n, 0); // 初始化计数数组
    for (int u = 0; u < n; ++u) {
        double max_w = W[u];
        int idx_max = u;
        // 直接通过索引访问邻居权重，无任何查找开销
        for (int v : adjacency[u]) {
            if (W[v] > max_w) {
                max_w = W[v];
                idx_max = v;
            }
        }
        X[idx_max]++;
    }
}

3. 简化逻辑提升可读性

原代码用三元运算符的写法非常晦涩，改成if语句不仅可读性更好，也不会带来性能损失，还能避免因运算符优先级导致的潜在bug。

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