如何计算嵌套循环的大O表示法？附单循环时间分析过程

好问题！先从你已经梳理清楚的单循环分析入手，咱们一步步拆解嵌套循环的时间复杂度，这样更容易衔接理解。

首先帮你提炼下单循环的核心：你提到的i赋值、条件判断、递增这些操作，每一步都是常数时间O(1)，所以单循环的总时间复杂度最终由循环执行的次数决定——不管是(n+1)次判断还是n次循环体执行，主导项都是n，所以单循环的大O是O(n)。

接下来看嵌套循环，核心思路其实和单循环一致：计算所有循环执行的总操作次数，然后保留最高次的主导项，忽略常数系数和低阶项。下面分几种常见情况具体说：

1. 内层循环次数和外层变量无关 #

这种是最直观的嵌套循环，外层循环跑n次，每次外层循环里，内层循环都固定跑m次（m可以是常数，也可以是和n相关的变量）。

举个代码例子：

for (int i = 0; i < n; i++) {
    // 外层循环执行n次
    for (int j = 0; j < n; j++) {
        // 内层每次执行n次，每次都是常数时间操作
        System.out.println("Hello");
    }
}

总操作次数是 n * n = n²，所以时间复杂度是O(n²)。如果内层是固定跑5次（常数），那总次数是5n，主导项还是n，复杂度就是O(n)。

2. 内层循环次数依赖外层循环变量 #

这种情况里，内层循环的执行次数会随着外层循环的变量变化而变化，需要用求和来计算总次数。

比如这个例子：

for (int i = 0; i < n; i++) {
    // 外层循环执行n次
    for (int j = 0; j <= i; j++) {
        // 第i次外层循环时，内层执行i+1次
        System.out.println("Hello");
    }
}

总操作次数是 1 + 2 + 3 + ... + n = n(n+1)/2，展开后是 (n² + n)/2。这里主导项是n²，常数系数1/2和低阶项n在大O表示法里会被忽略，所以时间复杂度还是O(n²)。

3. 内层/外层循环是对数级次数 #

有时候循环的递增不是+1，而是翻倍或者减半，这时候循环次数是对数级的，嵌套起来复杂度会变成O(n log n)。

比如这个例子：

for (int i = 1; i < n; i *= 2) {
    // 外层循环次数是log₂n次（i从1到n，每次翻倍，需要log2(n)步）
    for (int j = 0; j < n; j++) {
        // 内层每次执行n次
        System.out.println("Hello");
    }
}

总操作次数是 n * log₂n，所以时间复杂度是O(n log n)——这也是很多高效排序算法（比如归并排序、快速排序）的时间复杂度。

总结一下核心步骤 #

1. 先确定每一层循环的执行次数，尤其是内层循环是否依赖外层变量；
2. 计算所有循环的总执行次数，得到一个关于n的表达式；
3. 只保留表达式里的最高次项，忽略常数系数和低阶项，得到最终的大O表示法。

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