计算Big O时间复杂度时，nlogn与n²logn²是否属于同一量级？

你是对的，O(n log n) 和 O(n² log n²) 不属于同一量级，你同事的说法存在概念混淆。

大O量级的判断核心 #

大O时间复杂度描述的是算法运行时间随输入规模增长的上界，判断两个复杂度是否同量级的核心是：当输入规模变量n趋向于无穷大时，二者的比值是否为常数。

• 先对O(n² log n²)做化简：根据对数运算法则log(a^b) = b*log a，可得log n² = 2 log n，因此n² log n² = 2 n² log n，常数项2在大O表示中可以省略，所以O(n² log n²)等价于O(n² log n)。
• 计算二者比值：(n² log n) / (n log n) = n，当n趋向无穷大时，这个比值也会趋向无穷大，显然不是常数，所以二者完全不是同一量级，O(n² log n)的增长速度远快于O(n log n)。

你同事的混淆点在哪 #

他大概率是把「输入规模的变量定义」搞混了：

如果我们把原来的输入规模n替换为新的变量m = n²，那么原本O(n log n)的算法，在新的输入规模m下的复杂度确实是O(√m * log √m) = O(√m log m)，但这和「把原算法的输入规模从n扩大到n²」完全是两个概念。
后者的意思是输入规模变量还是原来的n，只是实际输入的大小变成了n²，那此时算法的时间复杂度就是O(n² log n²)，和原来的O(n log n)完全不等价。

实际案例验证 #

比如原本的算法是对长度为k的数组做归并排序，复杂度是O(k log k)：

• 当数组长度是100时，运算量大概是100 * log2(100) ≈ 700
• 当数组长度变成100² = 10000时，运算量大概是10000 * log2(10000) ≈ 140000
  后者是前者的200倍，显然不可能是同一量级。

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