T(n)=O(n log n)算法在输入规模m=n²时的复杂度求解正确性判断

你的推导过程和最终结果都是错误的，核心问题是对大O复杂度表示法的参数绑定规则存在概念误解。

你推导的第一步T(m) = m log m没有任何依据：

• 题目给出的T(n) = O(n log n)有严格的适用前提：这里的自变量n特指你最初选定的输入规模参数——布尔矩阵的边长，这个复杂度表达式描述的是运行时间随矩阵边长n的增长上界。你不能直接把表达式里的变量名替换成新的规模参数m，就默认运行时间随m的增长也满足m log m的关系，这是对大O记号的典型误用。

已知前置条件：

• 选取矩阵边长n作为输入规模参数时，算法运行时间上界为T = O(n log n)
• 新选取的输入规模参数m为矩阵总元素数，满足关系m = n²，即n = √m

将原复杂度表达式中的n统一替换为m的表达式：

1. 做变量替换：n = m^(1/2)，对应对数项log n = log(m^(1/2)) = (1/2)log m
2. 代入原时间上界公式：T = O( m^(1/2) * (1/2)log m )
3. 大O记号会自动忽略常数系数，因此化简后得到以m为规模参数的时间复杂度：T(m) = O(√m log m)

把m = n²代回上面得到的结果，可得T = O(√(n²) * log(n²)) = O(n * 2log n) = O(n log n)，和题目给出的初始条件完全一致，推导逻辑自洽。
而你之前得到的O(n² log n)换算为m的表达式是O(m log m)，相当于默认算法运行时间随矩阵总元素数呈m log m级增长，和题目给出的初始条件直接矛盾。

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