迭代次数为n²与4n的嵌套for循环的Big-O复杂度是多少

你的判断完全正确，这段代码的时间复杂度为 O(n³)。

给出的代码如下：

for (int i=0; i < n; i++) {
  for (int j=0; j < n*n; j++)
    sum += data[i] * data[j];
  for (int j=0; j < 4*n; j++)
    sum += data[i] + data[j];
}

大O记号的核心规则是只保留增长最快的最高阶项，忽略所有常数系数和低阶项，推导步骤如下：

• 外层for循环总共迭代 n 次
• 每轮外层循环中，两个独立内层循环的总执行次数为 n² + 4n，这里4n的增长速度远低于n²，属于低阶项可以直接忽略，因此每轮外层循环的时间复杂度为 O(n²)
• 内外层复杂度相乘得到总复杂度：O(n) * O(n²) = O(n³)

你可能会疑惑为什么4n和运算后产生的4n²项可以直接省略：大O记号描述的是输入规模n趋近于无穷大时的时间增长趋势，此时低阶项和常数系数对整体增长趋势的影响可以完全忽略，只需要保留最高阶的项即可。

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