Chapter 2 | Algorithm Analysis

criteria

• Input
• Output
• Definiteness
• Finiteness
• Effectiveness

2 Asymptotic Notation

[Definition] $T(N)=O(f(N))$ if there are positive constants $c$ and $N_0$ such that $T(N)\le c\ast f(N)$ for all $N\ge N_0$

[Definition] $T(N)=\mathrm{\Omega }(f(N))$ if there are positive constants $c$ and $N_0$ such that $T(N)\ge c\ast f(N)$ for all $N\ge N_0$

[Definition] $T(N)=\mathrm{\Theta }(f(N))$ if and only if $T(N)=O(f(N))$ and $T(N)=\mathrm{\Omega }(f(N))$

[Definition] $T(N)=o(p(N))$ if $T(N)=O(p(N))$ and $T(N)\ne \mathrm{\Theta }(p(N))$

if $T_1(N)=O(f(N))$ and $T_2(N)=O(g(N))$ then

(a) $T_1(N)+T_2(N)=max(O(f(N)),O(g(N)))$

(b) $T_1(N)\ast T_2(N)=O(f(N)\ast g(N))$

if $T(N)$ is a polynomial function, then $T(N)=\mathrm{\Theta }(N^k)$

中文刻画

🔑 四符号定义（基于标准 CLRS 表述）

符号	数学定义	直观含义	关键特征
O(g(n))	∃c>0, n₀: 0 ≤ f(n) ≤ c·g(n), ∀n≥n₀	渐近上界	“f 的增长不超过 g"（允许同阶）
Ω(g(n))	∃c>0, n₀: 0 ≤ c·g(n) ≤ f(n), ∀n≥n₀	渐近下界	“f 的增长不低于 g"（允许同阶）
Θ(g(n))	∃c₁,c₂>0, n₀: 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n), ∀n≥n₀	紧确界	“f 与 g 同阶增长"（上下界同时成立）
o(g(n))	∀c>0, ∃n₀: 0 ≤ f(n) < c·g(n), ∀n≥n₀	严格上界	“f 的增长严格慢于 g"（lim f/g = 0）

💡 记忆锚点：

• O / Ω / Θ：关注“存在某个常数 c"
• o：要求“对任意小的 c 都成立” → 更强的上界
• Θ = O ∩ Ω（同时满足上下界）

---

📌 经典案例验证

设 $f(n)=(\log n{)}^{100}$, $g(n)=n^{0.01}$：

• ✅ $f(n)=O(g(n))$：存在 $c=1$ 与足够大的 $n_0$，使 $f(n)\le c\cdot g(n)$（渐近成立）
• ✅ $f(n)=o(g(n))$：$\underset{n\to \mathrm{\infty }}{lim}\frac{(\log n{)}^{100}}{n^{0.01}}=0$（对任意 $c>0$，终将小于 $c\cdot g(n)$）
• ❌ $f(n)\ne \mathrm{\Omega }(g(n))$：不存在常数 $c$ 使 $f(n)\ge c\cdot g(n)$ 对所有大 $n$ 成立
• ❌ $f(n)\ne \mathrm{\Theta }(g(n))$：因不满足 $\mathrm{\Omega }$ 条件

→ 结论：$(\log n{)}^{100}=o(n^{0.01})\subset O(n^{0.01})$，体现“对数多项式增长严格慢于任意正幂次多项式”。

---

⚠️ 常见误区澄清

误区	正解
“O 仅表示最坏情况”	O 是纯数学符号。算法中常以 O 描述最坏时间复杂度，但符号本身与“最好/最坏”无关
“n = O(n²) 是错的”	正确。O 表示上界，$n$ 的增长速率确实不超过 $n^2$（如同“1万 ≤ 100万”为真）
“O 和 o 可互换”	关键区别：• $n=O(n)$ ✓（允许相等）• $n=o(n)$ ✗（要求严格小于，极限非零）
“小 n 时 f > g，故 f ≠ O(g)"	渐近分析仅关注 $n\to \mathrm{\infty }$ 的趋势，小规模行为不影响结论

---

💎 实践建议

• 描述算法复杂度：优先使用 Θ（若能证明紧确界），其次 O（最坏情况上界）
• 强调主导关系：用 o 表明“被显著主导”（如 $(\log n{)}^k=o(n^{\epsilon })$）
• 证明问题下界：使用 Ω（如比较排序 $\mathrm{\Omega }(n\log n)$）
• 避免模糊表述：不说“大约 $n^2$"，而说“时间复杂度为 $\mathrm{\Theta }(n^2)$"

时间复杂度计算

某分支提前终止

for (i=0; i < N*N/100; i++)      // 外层：i ∈ [0, N²/100)
    for (j = N; j > i; j--)      // 中层：仅当 i < N 时执行 (N - i) 次
        for (k=0; k < N*3; k++)  // 内层：固定 3N 次
            C += B;

Qwen-Max-Thinking

分析循环中“提前终止”（即内层循环因条件不满足而实际执行次数远低于声明范围）是算法复杂度分析的关键难点。核心原则：必须将内层循环的实际迭代次数表示为外层变量的函数，并通过求和精确计算总操作数，而非简单相乘循环上限。

---

🔑 分析步骤（以 Else 分支为例）

步骤 1️⃣：建立精确求和式

总操作数 =

$$\sum _{i=0}^{\lfloor N^2/100\rfloor -1}[\underset{\text{中层实际迭代}}{\underbrace{max(0,N-i)}}\times \underset{\text{内层迭代}}{\underbrace{3N}}]$$

步骤 2️⃣：拆分有效/无效区间（关键！）

• 有效区间（$0\le i<N$）：
  $max(0,N-i)=N-i>0$，中层循环体执行$$\sum _{i=0}^{N-1}(N-i)\cdot 3N=3N\cdot \frac{N(N+1)}{2}=\frac{3}{2}{N}^3+O(N^2)$$
• 无效区间（$N\le i<N^2/100$）：
  $max(0,N-i)=0$，循环体不执行。仅剩：
  • 中层循环条件判断 1 次/外层迭代 → $O(1)$
  • 外层迭代次数 $\approx N^2/100-N=\mathrm{\Theta }(N^2)$
    → 总开销 $\mathrm{\Theta }(N^2)$（低阶项）

步骤 3️⃣：合并并取主导项

$$\text{总操作数}=\underset{\text{有效区间}}{\underbrace{\frac{3}{2}{N}^3+O(N^2)}}+\underset{\text{无效区间}}{\underbrace{O(N^2)}}=\mathrm{\Theta }(N^3)$$

无效区间的 $\mathrm{\Theta }(N^2)$ 被 $\mathrm{\Theta }(N^3)$ 主导，可忽略。

---

📌 通用分析框架（适用于所有“提前终止”场景）

步骤	操作	关键问题
1. 建模	写出总操作数的求和表达式	内层迭代次数如何依赖外层变量？（如 $f(i)=max(0,N-i)$）
2. 拆分	求解 $f(i)>0$ 的区间	何时循环体实际执行？解不等式（如 $i<N$）
3. 分段求和	分别计算有效/无效区间的贡献	无效区间是否含非平凡开销？（如条件判断、函数调用）
4. 阶数比较	保留最高阶项	低阶项（如 $\mathrm{\Theta }(N^2)$ vs $\mathrm{\Theta }(N^3)$）是否可忽略？
5. 验证边界	检查小 $N$ 是否影响渐近结论	渐近分析关注 $N\to \mathrm{\infty }$，小 $N$ 不影响大 $O$

---

⚠️ 常见陷阱与应对

陷阱	错误做法	正确做法
盲目相乘循环上限	$(N^2)\times N\times N=O(N^4)$	分析内层实际迭代次数函数 $f(i)$
忽略无效区间开销	假设“不执行=无开销”	检查条件判断/初始化是否含高成本操作（本例中仅为 $O(1)$）
误判有效区间范围	认为 $i$ 从 $0$ 到 $N^2/100$ 全部有效	严格解不等式：$j>i$ 且 $j$ 从 $N$ 开始 → 仅 $i<N$ 有效
混淆“循环声明次数”与“循环体执行次数”	用外层循环次数代表总复杂度	聚焦循环体内语句的实际执行总次数

---

💡 实用技巧

1. 画小规模示例：取 $N=5$ 手动计算各 $i$ 对应的内层执行次数，快速发现规律。
2. 用数学工具简化：
   • 等差数列求和：$\sum _{i=0}^{N-1}(N-i)=N(N+1)/2$
   • 积分近似（大 $N$）：$\sum _{i=0}^{N}f(i)\approx {\int }_0^{N}f(x)dx$
3. 代码重写验证：

   // 等价转换：仅当 i < N 时进入中层循环
   for (i=0; i < min(N, N*N/100); i++) 
       for (j=i+1; j<=N; j++) 
           for (k=0; k<3*N; k++) ...

   直接暴露有效范围，复杂度一目了然。

✅ 核心心法：时间复杂度取决于算法实际执行的基本操作总数，而非循环语法的表面结构。遇到“提前终止”，立即问：“对每个外层索引 $i$，内层循环体究竟执行多少次？” —— 答案藏在循环条件与变量依赖关系中。掌握此思维，可破解绝大多数循环复杂度陷阱。