选择排序时间复杂度疑问：嵌套循环为何相加而非相乘？

• 你搞错了嵌套循环复杂度计算的核心逻辑：不是所有嵌套循环都直接用外层循环次数乘以内层循环次数，得看内层循环的执行次数是否固定。
• 选择排序的实际执行过程：
  • 外层循环从第1个元素遍历到倒数第2个元素，总共执行n-1次（时间复杂度层面可简化为O(n)）。
  • 每一轮外层循环中，内层循环的次数是逐轮递减的：第1轮内层循环对比n-1次，第2轮对比n-2次……最后1轮只对比1次。
• 总操作次数是各轮内层循环次数的总和：(n-1)+(n-2)+...+1 = n(n-1)/2，展开后是(n² - n)/2。根据时间复杂度的规则，我们只保留最高阶项并忽略常数和低阶项，最终时间复杂度就是O(n²)。
• 你之前的误解在于把“外层循环的执行次数”和“内层循环的总执行次数”当成两个独立的复杂度来相加，这是错误的——前者是循环的轮数，后者是所有轮次内层操作的总和，两者本质是包含关系，不是并列的两个复杂度。而如果强行用外层次数乘以内层单次的最大次数（比如n * n），得到的n²其实和求和后的最高阶项一致，并不会出现O(n³)的情况，问题出在你错误地把内层总次数当成了单次内层的复杂度，才会算出n * n(n-1)/2这种错误式子。

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