找到对称矩阵的最大元素的最有效算法是什么

Question

我实际上想知道如何在 C++ 中选择矩阵的最大整数（具有较大值的那个）的最佳方法，这种数据结构是 map<string, map<string,int>>，两者都按字典顺序排列。实际上我的函数 returns 是最大元素被索引的一对。感谢您的宝贵时间，对于我的英语水平不足感到抱歉。

Answer 1

搜索整个矩阵 (O(n²)) 将是：

std::map<std::string, std::map<std::string,int>> matrix;

int m = matrix.begin()->second.begin()->second; // Assuming non empty
for (const auto& row : matrix) {
    for (const auto& p : row.second) {
        m = std::max(m, p.second);
    }
}

map 没有随机访问，所以你不能像普通矩阵那样简单地做

for (int i = 0; i != size; ++i) {
    for (int j = i; j != size; ++j) {
        // ...
    }
}

但您可以使用 lower_bound 来 "possibly" 加速：

std::map<std::string, std::map<std::string,int>> matrix;

int m = matrix.begin()->second.begin()->second; // Assuming non empty
for (const auto& row : matrix) {
    for (auto it = row.second.lower_bound(row.first);
         it != row.second.end();
         ++it) {
        m = std::max(m, (*it).second);
    }
}

可能是 O(n*(log(n) + n/2))，它仍然是 O(n²)，具有较低的因子 (1/2)，但比较键（是字符串...）

找到对称矩阵的最大元素的最有效算法是什么

What is the most efficient algorithm to find the max element of a Symetric Matrix

c++

matrix

coding-efficiency