algorithm - 使用较少的比较查找最大值二维数组 N*N

Question

我想用较少的比较在 C 中的二维数组 N*N 中找到最大值。我可以简单地使用 O(N^2) 算法来完成，但我认为它太慢了。

于是，我又想了一个办法。我简单的循环一次，同时按行和列搜索，尽量降低复杂度。 (我猜 O(2(n-1)))你可以在这张图片中看到我正在尝试做什么。

我使用相同的循环来检查列和行的内容。

我想知道有没有更快的？喜欢用 O(N log N) 复杂度对二维数组进行排序？假设值未排序。

Answer 1

如果 M x M 元素的二维数组没有以任何方式排序，那么你不会比 O(M^2) 做得更好。

请记住，矩阵有 M^2 个元素，因此对它们进行排序的复杂度为 O(M^2 log M^2)，因为最合适的排序是 O(N log N)，这里 N = M^ 2.