循环中Math.max()处理递减元素时的时间复杂度评估问题

针对你提出的问题，直接结论是：这段代码的总时间复杂度是O(n²)，而非O(n*m)，原因如下：

1. 拆解总操作次数：

   • 循环执行n次，第1次调用Math.max()时，待处理的数组长度是n；第2次是n-1；……最后1次是1。
   • 总操作次数是等差数列求和：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2

2. 渐近复杂度的简化规则：
   时间复杂度关注的是渐近上界，会忽略常数系数和低阶项。n(n+1)/2展开后是(n² + n)/2，其中n²是主导项，所以最终的时间复杂度为O(n²)。

你提到的O(n*m)并不适用，因为m不是一个固定值，而是随着循环迭代持续递减的变量，不能直接将两个变量相乘来评估复杂度。

示例代码验证：

const arr = [1,2,3,4,5];
const n = arr.length;

for (let i=0; i<n; i++) {
   const max = Math.max(...arr);
   arr.pop();
   console.log({arr,max});
}

这段代码中，Math.max(...arr)会把数组展开为参数，其时间复杂度确实等于当前数组的长度m，而循环次数是n次，总操作数的求和结果对应O(n²)的复杂度。

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