Java二维数组方法时间复杂度分析：确定运行时依赖的n值

先贴出待分析的Java代码：

public static void method(char[][] c) {
    if (c.length >= c[0].length) {
        for(int i = 0; i < c[0].length; i++) {
            c[i][i] = '*';
            c[i][c[0].length -1-i] = '*';
        }
    } else {
        for(int i = 0; i < c.length; i++) {
            c[i][i] = '*';
            c[c.length -1-i][i] = '*';
        }
    }
}

直接拆解问题：
这个方法的核心执行逻辑是循环内的两次赋值操作，循环的执行次数完全由行数（c.length）和列数（c[0].length）中的较小值决定。

逐一分析三种有问题的n定义：

• 若n定义为c.length（行数）：当列数比行数小时，循环次数等于列数，和n无关，此时O(n)的结论不成立，显然错误。
• 若n定义为c[0].length（列数）：当行数比列数小时，循环次数等于行数，和n无关，同样O(n)的结论不成立，也错误。
• 若n定义为c.length * c[0].length（数组总元素数）：循环次数是min(行数,列数)，这个值远小于总元素数（除非是方阵），时间复杂度应该是O(√n)，和你认定的O(n)不符，所以这个定义也不对。

正确的n定义应该是行数和列数中的较小值，也就是n = min(c.length, c[0].length)。此时循环执行n次，每次循环是两个O(1)的赋值操作，总时间复杂度就是O(n)，完全匹配你的结论。

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