以Big Θ分析时间复杂度：遍历i、j时while循环理解求助

安全阿岳

2026-5-20

处理嵌套遍历与while循环的思路及时间复杂度分析

一、理清嵌套遍历+while循环逻辑的实用思路

我当初刚接触这类嵌套结构时也经常卡壳，分享几个亲测有效的方法：

拆解步骤，逐行跟踪：找个极小的测试用例（比如i从0到2，n=3），拿纸笔或者在代码注释里写下每一步i、j的取值，以及while循环的执行次数。比如针对这类典型结构：
```
for (int i = 0; i < n; i++) {
    int j = i + 1;
    while (j < n && arr[j] < arr[i]) {
        j++;
    }
    // 后续操作
}
```
逐行跟踪：i=0时j从1开始，每次检查条件并自增直到不满足；i=1时j从2开始重复过程；i=2时j初始为3，直接跳出while。一步步走下来，很容易看清while循环如何跟着i的变化调整执行路径。
明确while循环的“使命”与边界：先搞清楚这个while在嵌套结构里的作用——是找特定元素？还是扩展范围？再确认它的起始状态（比如j的初始值是否和i绑定）、触发条件、终止条件。把这些和外层for循环的逻辑绑定起来看，就能明白两者的协作关系。
等价转换为for循环（如果可行）：有些while循环可以改写成for循环，结构会更直观。比如上面的while可以写成：for(; j < n && arr[j] < arr[i]; j++);，这样你能更清晰看到j的变化范围和i的关联。

分析嵌套结构的时间复杂度，核心是统计所有循环执行的总次数，再提炼出和输入规模n相关的渐近表达式：

还是拿刚才的例子来说：

外层for循环固定执行n次（i从0到n-1）。
对于每个i，while循环的执行次数取决于j从i+1开始到终止的步数。最坏情况下，每次while都要执行到j=n-1：i=0时j跑n-1次，i=1时跑n-2次……i=n-2时跑1次，i=n-1时跑0次。
总次数为 1+2+...+(n-1) = n(n-1)/2，这属于Θ(n²) 复杂度——因为我们只关注最高阶项，忽略低阶项和常数系数。

如果while循环的终止条件很快满足（比如arr[j] >= arr[i]在j=i+1时就成立），那每个while只执行1次，总次数就是n次，复杂度为Θ(n)。但大Θ通常默认关注最坏情况，除非题目特别说明平均情况。

当外层循环和内层while的变量有依赖关系（比如j从i开始），要计算累加和；如果变量完全独立（比如外层for i到n，内层while j从0到m），总次数就是nm，复杂度为Θ(nm)。
记住几个常见累加和对应的复杂度：1+2+...+n = Θ(n²)，1*n = Θ(n)，log级别的累加次数对应Θ(logn)。

假设代码如下：

int count = 0;
for (int i = 0; i < n; i++) {
    int j = i;
    while (j < n && arr[j] % 2 == 0) {
        count++;
        j++;
    }
}

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