关于循环BigO计算的疑问：内外循环运算计数逻辑为何不一致？

我正在学习BigO复杂度计算，针对下面这段代码的最坏情况（数组无重复元素，长度为n），书中给出的运算量统计是：

• 外层循环：4n次运算
• 内层循环：n*(n*8) = 8n²次运算
• 总运算量：4n + 8n²次运算

但我有个疑问：既然外层循环的4次运算包含1次赋值、1次比较、2次增量操作，那为什么不能按“外层4n × 内层8n”来算总运算量（得到32n²），而是外层加内层的结果？

代码片段 #

public boolean containsDuplicates(int[] numbers) {
     for (int i=0; i<numbers.length; i++) { // 4 operations
       for (int j=0; j<numbers.length; j++) { // 4 operations
         if (i != j && numbers[i] == numbers[j]) return true; // 4 operations
     }
   }
  return false;
}

原因解析 #

关键要搞清楚运算量的统计范围：

• 外层循环的4n次，是外层for循环自身所有操作的总和：涵盖i的初始化、每次循环的条件判断、i的增量操作，把这些步骤全部加起来总共是4n次。
• 内层循环的8n²次，是所有内层循环迭代里操作的总和：每次外层循环会触发n次内层循环，而每次内层循环里，既有内层for的4次操作（j的初始化、条件判断、增量），还有if语句的4次操作（i≠j的判断、数组元素取值、元素比较，最坏情况不会触发返回，所以这4次每次都执行），所以每次内层迭代是8次操作，n次外层迭代×n次内层迭代=8n²次。

这两部分是独立的操作集合：外层循环的操作是控制外层迭代的逻辑，内层循环的操作是每次外层迭代里执行的具体内容，两者是相加关系，不是相乘。就像你先完成4n项基础操作，然后在每一轮外层操作里再完成8n项内层操作，总工作量就是4n + n×8n = 4n+8n²，而非4n和8n的乘积。

内容的提问来源于stack exchange，提问作者Soner from The Ottoman Empire