了解矩阵解的时间复杂度

Question

研究了一种算法，该算法需要计算矩阵中连续1的最长数。提供的解决方案描述和解决方案如下：

蛮力方法非常简单。我们直接遍历给定矩阵中的每一条有效线：即水平、垂直、中间对角线上下的对角线、中间反对角线上下的反对角线。每次遍历过程中，如果遇到连续的1，我们会不断增加计数。我们会为遇到的任何不连续重置计数。在这样做的同时，我们还跟踪迄今为止发现的最大计数。

public class Solution {
    public int longestLine(int[][] M) {
        if (M.length == 0)
            return 0;
        int ones = 0;
        //horizontal
        for (int i = 0; i < M.length; i++) {
            int count = 0;
            for (int j = 0; j < M[0].length; j++) {
                if (M[i][j] == 1) {
                    count++;
                    ones = Math.max(ones, count);
                } else
                    count = 0;
            }
        }
        //vertical
        for (int i = 0; i < M[0].length; i++) {
            int count = 0;
            for (int j = 0; j < M.length; j++) {
                if (M[j][i] == 1) {
                    count++;
                    ones = Math.max(ones, count);
                } else
                    count = 0;
            }
        }
        //upper diagonal
        for (int i = 0; i < M[0].length || i < M.length; i++) {
            int count = 0;
            for (int x = 0, y = i; x < M.length && y < M[0].length; x++, y++) {
                if (M[x][y] == 1) {
                    count++;
                    ones = Math.max(ones, count);
                } else
                    count = 0;
            }
        }
        //lower diagonal
        for (int i = 0; i < M[0].length || i < M.length; i++) {
            int count = 0;
            for (int x = i, y = 0; x < M.length && y < M[0].length; x++, y++) {
                if (M[x][y] == 1) {
                    count++;
                    ones = Math.max(ones, count);
                } else
                    count = 0;
            }
        }
        //upper anti-diagonal
        for (int i = 0; i < M[0].length || i < M.length; i++) {
            int count = 0;
            for (int x = 0, y = M[0].length - i - 1; x < M.length && y >= 0; x++, y--) {
                if (M[x][y] == 1) {
                    count++;
                    ones = Math.max(ones, count);
                } else
                    count = 0;
            }
        }
        //lower anti-diagonal
        for (int i = 0; i < M[0].length || i < M.length; i++) {
            int count = 0;
            for (int x = i, y = M[0].length - 1; x < M.length && y >= 0; x++, y--) {
                //System.out.println(x+" "+y);
                if (M[x][y] == 1) {
                    count++;
                    ones = Math.max(ones, count);
                } else
                    count = 0;
            }
        }
        return ones;

    }
}

复杂性分析

时间复杂度：O（n^2）我们沿着整个矩阵遍历4次。空间复杂度：O（1）。使用恒定空间。

如果我们简单地遍历每一行的矩阵

Answer 1

我认为你的困惑来自这样一个事实，即有n²元素，而不是n。

该算法访问每个元素的次数有限。可以说它在元素数量上是线性的，因此在n中是二次的。

Answer 2

什么是？

矩阵是正方形吗？
如果是，则n是矩阵的宽度/高度。
如果不是，则需要m和n，独立表示宽度和高度。

假设它不是正方形的。

如果将宽度翻倍（m），代码中会发生什么？
迭代总数翻倍，因此性能与m成线性关系。

如果将高度加倍（n），代码中会发生什么<总迭代次数加倍，因此性能与n成线性关系。

结论：性能为O（mn）

当然，如果n是矩阵中的值数，则性能为O（n）。