判断特殊n×n 0-1矩阵1计数Java代码的时间复杂度

问题背景 #

给定一个n×n的0-1矩阵，满足以下两个条件：

• 每行中所有1都位于0之前
• 第i行的1的数量≥第i+1行的1的数量

已编写一段能正确统计矩阵中1总数的Java代码，但不确定其时间复杂度是O(n)还是O(n²)，以下是相关示例矩阵、代码及运行输出，请求判断时间复杂度。

示例矩阵 #

{{1,1,1,1},
 {1,1,1,1},
 {1,1,0,0},
 {1,0,0,0}}

Java代码 #

public class SpecialMatrix {

    public static void main(String[] args) {
        int[][] a = {{1,1,1,1},
                     {1,1,1,1},
                     {1,1,0,0},
                     {1,0,0,0}};
        
        int n = 4;
        int cnt=0;
        int row; 
        int col = 0;
        for (row = n-1; row>=0; row--)
        {
            while(col<n && a[row][col]==1)
            {
                cnt = cnt + (row + 1);
                System.out.print("Row: " + row + " Col: " + col + " Cnt: " + cnt);
                System.out.println();
                col++;
            }
            System.out.println();
        }
        System.out.print(cnt);
        
    }
        
}

运行输出 #

Row: 3 Col: 0 Cnt: 4

Row: 2 Col: 1 Cnt: 7

Row: 1 Col: 2 Cnt: 9
Row: 1 Col: 3 Cnt: 11


11

时间复杂度判断 #

这段代码的时间复杂度是O(n)，核心原因如下：

• 外层循环从最后一行遍历到第一行，共执行n次，但内层while循环的总执行次数不会超过n次。
• 变量col是全局维护的，只会从0单向递增到n-1，不会回溯。也就是说，整个程序运行期间，while循环的迭代次数总和最多为n（比如矩阵全为1的极端情况）。
• 结合外层循环的n次操作，总操作次数是线性的O(n)，远低于O(n²)的量级。

补充逻辑：因为矩阵满足“第i行1的数量≥第i+1行”的约束，从下往上遍历时，当前行的1的结束位置不会超过上一行的1的结束位置，因此col不需要回退，保证了内层循环的总次数是线性的。

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