分析给定代码时间复杂度时拆分出好坏场景，与标准答案不符哪里出错？

问题代码 #

for (int i = 0; i < 2*n; i++) {
   if (i == n){
     for (int j = 0; j < i; j++) {
       for (int k = 0; k < i; k++) {
          O(1);
       }
     }
   }
   else {
     for (int j = 0; j < i; j++) {
       O(1);
     }
   }
}

你的分析错误点 #

你核心的错误是对分支1的执行次数计数错误：外层for循环中i == n的判断只会命中1次，并不是n次，你推导时给分支1的计算式额外乘了n的系数，才得到了错误的O(n³)结果。
另外你提到的“最好/最坏时间复杂度”也不成立，这段代码的执行逻辑完全由n决定，没有和输入动态相关的分支选择，执行路径是固定的，不存在不同场景的复杂度差异。

正确复杂度计算 #

我们直接对所有执行的操作数求和即可：

1. 外层i从0遍历到2n-1，共2n次迭代：
   • 当i≠n时，共2n-1次迭代，每次内层执行i次O(1)操作，这部分总操作数为：
     ∑（i从0到2n-1且i≠n）i = (2n-1)*2n/2 - n = 2n² - 2n
   • 当i==n时，仅触发1次，两层嵌套循环共执行n*n = n²次O(1)操作
2. 总操作数求和：2n² - 2n + n² = 3n² - 2n，忽略低阶项和常数系数后，时间复杂度为O(n²)，和参考答案一致。

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