了解矩阵解的时间复杂度

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）。使用恒定空间。

如果我们只是遍历矩阵的每一行和col，那么我们就知道它不是二次算法。二次方的工作是否发生是因为每个对角线触摸了N次元素？

Answer 1

什么是n？

矩阵是正方形吗？ 如果是，那么n是矩阵的宽度/高度。 如果不是，那么你需要m和n，分别代表宽度和高度。

让我们说这不是正方形。

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

如果你加倍高度（n），代码会发生什么？ 迭代总数加倍，因此性能与n呈线性关系。

结论：性能是O（mn）

---

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

Answer 2

我认为你的困惑来自于n²元素，而不是n。

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