本文系统讲解嵌套循环时间复杂度的计算原理，明确指出：无论内层循环是否依赖外层变量，本质都是对“所有执行单元操作次数”的求和；当内层迭代次数恒定为M时，总和自然简化为N×M；当内层次数随i变化（如1到i）时，则需累加∑ᵢ₌₁ᴺ i，最终仍归于大O下的主导项判定。
本文系统讲解嵌套循环时间复杂度的计算原理，明确指出：**无论内层循环是否依赖外层变量，本质都是对“所有执行单元操作次数”的求和；当内层迭代次数恒定为m时，总和自然简化为n×m；当内层次数随i变化（如1到i）时，则需累加∑ᵢ₌₁ᴺ i，最终仍归于大o下的主导项判定。**
在Java算法分析中，嵌套循环的时间复杂度（Time Complexity, TC）常被初学者误认为存在“乘法规则”和“加法规则”两种独立逻辑。实际上，不存在“何时相乘、何时相加”的二元选择——只有一种根本方法：统计最内层循环体被执行的总次数，并用大O记号提取其数量级。 所谓“乘”或“求和”，不过是该总数在不同场景下的数学表达形式。
✅ 正确理解：总执行次数 = 对所有外层状态的内层迭代数求和
设外层循环变量为 i，取值范围为 i ∈ [1, N]，对每个 i，内层循环执行 f(i) 次（f(i) 可为常数，也可为含 i 的表达式），则总操作数为：
T(N) = f(1) + f(2) + f(3) + … + f(N) = Σᵢ₌₁ᴺ f(i)
-
Case 1：内层迭代次数恒定（如 Code 1）
f(i) = M（与 i 无关）→
T(N) = Σᵢ₌₁ᴺ M = M × N → TC = O(N×M)
示例：for (int i = 0; i < N; i++) { // 外层：N次 for (int j = 0; j < M; j++) { // 内层：每次固定M次 System.out.println(i + "," + j); // 核心操作：1次 } }总输出语句执行 N × M 次，无歧义。
-
Case 2：内层迭代次数依赖外层变量（如 Code 2）
f(i) = i（常见于 j <= i 或 j < i 结构）→
T(N) = Σᵢ₌₁ᴺ i = N(N+1)/2 = (N² + N)/2 → TC = O(N²)（高阶项主导）
示例：for (int i = 1; i <= N; i++) { // i = 1, 2, ..., N for (int j = 1; j <= i; j++) { // 对每个i，内层执行i次 System.out.print("*"); // 核心操作：1次 } System.out.println(); }输出三角形星号：第1行1个，第2行2个，…，第N行N个 → 总星号数 = 1+2+...+N = N(N+1)/2 ∈ O(N²)。
立即学习“Java免费学习笔记（深入）”；
❗ 关键澄清：你提出的“Outer loop + inner loop”相加（即 N + N(N+1)/2）是错误的。外层循环本身的控制开销（如 i++、条件判断）属于低阶操作，已被计入 f(i) 的隐含常数因子中；大O分析关注的是最内层可变操作的渐进增长，而非各层开销简单叠加。因此，N + N(N+1)/2 中的 N 项在 O(N²) 面前可直接忽略。
⚠️ 常见误区与注意事项
误区1：“依赖就要求和，不依赖就相乘”
→ 实质仍是求和：N×M = Σᵢ₌₁ᴺ M，只是因 f(i) 恒定而简化为乘法。乘法是求和的特例，不是并列规则。误区2：混淆循环变量范围与输入规模
如 for (int i = low; i <= high; i++)，迭代次数为 high−low+1，应记为 n，TC = O(n)，而非O(1)——即使传入具体数字，只要该范围随输入数据量线性增长，即为线性复杂度。陷阱：非典型嵌套（如内层条件提前终止）
若内层循环含 break 或 return，且终止概率与 i 相关（如查找成功即退出），则需按最坏情况（Worst Case）分析：假设永不提前终止，再验证是否可优化。面试中必须主动说明前提。
? 实战检验：快速判断三步法
- 锁定最内层核心操作（如 arr[i][j] = ...、sum += ...）；
- 写出该操作被执行的总次数表达式：Σᵢ f(i)，其中 f(i) 是“当外层为 i 时，内层执行多少次”；
- 化简表达式，保留最高阶项，去掉常系数 → 即为 Big O 结果。
例如：
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) { // f(i) = n − i
process(i, j);
}
}
// T(n) = Σᵢ₌₀ⁿ⁻¹ (n−i) = n + (n−1) + ... + 1 = n(n+1)/2 → O(n²)掌握这一本质视角，你将发现：递归、分治、动态规划的复杂度分析，同样遵循“统计总操作数 → 提取主导项”的统一逻辑。多写几组小数据手动模拟执行次数（如 N=3,5,10），比死记公式更助你建立直觉。
