嵌套循环时间复杂度计算疑问：何时相乘何时求和？

关于你的计算思路是否正确 #

你给出的计算方式：N + N(N+1)/2 = 2N + N²，最终忽略低阶项得到O(N²)，这个结果是正确的。不过从逻辑严谨性来说，我们统计时间复杂度时，核心关注的是嵌套循环中最内层操作的总执行次数（比如内层循环体的代码），外层循环的初始化、条件判断等操作属于低阶项，即使不加入计算，最终的大O复杂度依然是O(N²)。所以你的思路没问题，最终结论正确。

嵌套循环：相乘 vs 求和的判断标准 #

核心原则是：总执行次数等于外层循环每次迭代时，内层循环执行次数的总和，以此为基础区分两种场景：

1. 相乘的场景（内层次数与外层无关） #

当内层循环的执行次数不随外层循环的变量变化时，外层每迭代1次，内层都会固定执行M次。总执行次数就是外层迭代次数 × 内层单次迭代次数，也就是N*M，时间复杂度为O(N*M)（对应你给出的Code 1）。

示例代码（修正变量名错误）：

for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
        // 内层操作
    }
}

2. 求和的场景（内层次数依赖外层） #

当内层循环的执行次数由外层循环的变量决定时，需要把外层每次迭代时内层的执行次数累加起来。比如Code 2中，外层第i次迭代时，内层执行i次，总次数就是1+2+...+N = N(N+1)/2，时间复杂度为O(N²)。

示例代码：

for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= i; j++) {
        // 内层操作
    }
}

简单总结：内层次数固定就相乘，内层次数随外层变量变化就求和，本质都是计算内层核心操作的总执行次数。

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