本文详解在分析算法时间复杂度时，为何必须明确定义“n”的实际含义；以一个对二维 char 数组进行对角线赋值的 java 方法为例，阐明其真实输入规模应为行数与列数的最大值，而非随意选取单一维度或乘积。
本文详解在分析算法时间复杂度时，为何必须明确定义“n”的实际含义；以一个对二维 char 数组进行对角线赋值的 java 方法为例，阐明其真实输入规模应为行数与列数的最大值，而非随意选取单一维度或乘积。
在算法分析中，O(n) 这类表达式看似简洁，实则隐含重大前提：n 必须被明确定义为某个可度量、与输入直接相关的规模参数。脱离定义谈“复杂度是 O(n)”是不严谨甚至误导性的——它掩盖了问题本质，也阻碍了对算法行为的准确建模。
回到给出的代码：
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 的主对角线和反对角线（在可行范围内）执行常数时间赋值操作。关键观察在于：
循环执行次数取决于 min(c.length, c[0].length) 吗？不完全是。
实际上，两个分支分别以 c[0].length 和 c.length 为循环上限，且仅当 i 同时满足行索引与列索引有效时才安全访问（例如 c[i][i] 要求 i < c.length && i < c[0].length）。但代码中未做越界检查，因此其正确运行的前提是：输入 c 为方阵，或至少保证在循环范围内所有 c[i][j] 访问合法。我们按题设默认输入有效，聚焦于主导运行时间的循环次数。第一分支（c.length ≥ c[0].length）执行 c[0].length 次迭代；
第二分支（c.length < c[0].length）执行 c.length 次迭代。
因此，总迭代次数为 min(c.length, c[0].length)？错——注意条件判断本身是 O(1)，而循环次数由 max(c.length, c[0].length) 的较小者决定，即 min(c.length, c[0].length)。但等等：再看循环体内部操作，每次迭代执行两次数组赋值（均为 O(1)），无嵌套。故总时间正比于 min(m, n)，其中 m = c.length, n = c[0].length。
然而，这仍非最佳建模方式。真正影响算法“规模感”的，是输入所承载的信息总量或结构约束。对于二维数组，常见输入规模参数有三类：
| 参数 | 含义 | 是否适用本例 |
|---|---|---|
| N = c.length | 行数 | ❌ 单独使用忽略列约束，无法保证 c[i][i] 有效 |
| M = c[0].length | 列数（假设非空） | ❌ 同理，忽略行数限制 |
| T = c.length × c[0].length | 总元素数 | ⚠️ 过度保守：算法并未遍历全部元素，仅触及至多 2 × min(m,n) 个位置 |
| K = min(c.length, c[0].length) | 可安全访问的对角线长度 | ✅ 最贴合实际执行步数 |
✅ 结论：该算法的时间复杂度为 O(k)，其中 k = min(c.length, c[0].length)。
更严谨地，应表述为：
method 的运行时间是 O(min(m, n))，其中 m = c.length（行数），n = c[0].length（列数），且假设 c 非空、c[0] 存在。
⚠️ 注意事项：
- 若强行归约为单变量 n，必须附加说明，例如：“令 n = min(c.length, c[0].length)”，否则 O(n) 无意义；
- c.length * c[0].length 是输入的空间规模，但本算法是典型的“输出敏感”或“结构敏感”类型，并不扫描整个矩阵，故不应作为时间复杂度基准；
- 实践中，若上下文明确处理的是 n×n 方阵，则可自然取 n 为边长，此时复杂度简化为 O(n)；但原始代码未限定方阵，因此不可假设。
总结：定义 n 不是技术细节，而是建模的第一步。优秀的复杂度分析始于清晰的问题刻画——明确“什么在变？怎么变？变多少？”唯有如此，O(·) 才是从数学工具升华为工程洞察的桥梁。
