渐近记号基础与比较

• 各表达式化简为等价的简单形式
• 取对数比较与极限比值法
• 处理 ε→0+ 的极端情形

逐步化简：n^(1/log n) = n^(1/log n) = e^(ln n / log n) = e^(ln n / (ln n/ln 2)) = e^(ln 2) = 2，是常数，增长最慢。2^(log n) = n（因 2^(log₂n)=n），增长为 n。log(n!) ≈ n log n − n ln 2 + O(1)（Stirling），与 n log n 同阶。n log n 是 n·log n。n^(1/ε) 当 ε→0+ 时指数 1/ε→∞，故 n^(1/ε)=n^∞，增长为超多项式（指数级），最快。最复杂的是 (log n)^log n：取对数得 log((log n)^log n) = log n·log(log n)，而 log(n log n) = log n + log log n，前者增长更快，故 (log n)^log n 增长快于 n log n。排序（低到高）：n^(1/log n)=2（常数）< 2^(log n)=n < log(n!) ~ n log n < (log n)^log n < n^(1/ε)（ε→0+，超多项式）。

关键技巧是取对数比较：n^(1/log n) 化简为常数 2，2^(log n) 化简为 n，log(n!) 用 Stirling 等同 n log n，(log n)^log n 取对数后是 log n·log log n，比 n log n 的对数（log n + log log n）更大。n^(1/ε) 即使 ε 略大于 0 也是超多项式，故排在最后。

• o 与 O 的定义差异（o 是严格上界，O 是上界）
• 极限比值：f/g→0（o）与 f/g≤c（O）
• 反例：f(n)=g(n) 时 f=O(g) 但 f≠o(g)

本质区别：O(g) 表示 f 的上界是 g 的常数倍，即存在 c>0、n₀ 使 0≤f(n)≤c·g(n) 对所有 n≥n₀ 成立；o(g) 表示 f 相对 g 是"严格更小"，即 lim f(n)/g(n)=0。O 允许 f 与 g 同阶（可差常数因子），o 要求 f 渐近小于 g 且不可同阶。反例：取 f(n)=g(n)=n，则 f(n)=O(g(n))（取 c=1 成立），但 f(n)≠o(g(n))，因为 lim f/g=1≠0。更一般地，任何 f=Θ(g) 的函数都满足 f=O(g) 但 f≠o(g)。另一个例子：f(n)=2n，g(n)=n，f=O(g) 但 f/g→2≠0，故 f≠o(g)。

O 是"上界"，包含同阶；o 是"严格更小"，排除同阶。用极限比值最清晰：f=O(g) 当且仅当 limsup f/g 有限；f=o(g) 当且仅当 lim f/g=0。当 f 与 g 同阶（比值趋近非零常数）时，f=O(g) 成立但 f=o(g) 不成立。

• O 作为上界的安全性与普遍性
• Θ 作为紧确界的精确性
• 何时 Θ 更适用

算法分析通常上报最坏情况上界 O，因为：①O 是"保证"，告诉用户算法在最坏情况下不会超过某个界，这对性能承诺是安全的；②即使算法在不同输入上性能波动，O 上界仍成立，且简单易得；③Θ 是紧确界，需要证明上界和下界都匹配，多数情况下下界更难证明。当算法性能对所有输入都一致（即最坏与最好同阶）时 Θ 更有信息量，例如归并排序、堆排序在所有输入上都是 Θ(n log n)，此时 Θ 提供了精确描述；再如二分查找、遍历数组等最优最坏同为 Θ 的算法。此外若要强调"算法的最佳可能性能"或做最坏情况等同于典型情况时，Θ 更精确。

O 侧重"上限保证"，Θ 侧重"精确刻画"。当最坏与最好渐近不同（如快速排序最坏 Θ(n²)、最好 Θ(n log n)）时，用 Θ 会误导（无法同时为真），故用 O 报最坏上界。当所有输入行为一致时 Θ 同时给出上下界，更富信息。

• 渐近记号忽略常数因子
• 常数因子与输入规模的关系
• 实测与渐近分析的取舍

渐近记号 O、Θ、Ω 只描述函数随 n 增长的趋势，忽略常数因子。一个 O(n log n) 的算法若常数因子很大（如 10⁶·n log n），其实际运行时间在小到中等输入规模下可能远大于一个常数因子很小的 O(n²) 算法（如 0.5·n²）。当输入规模 n 小于某个交叉点 n₀ 时，O(n²) 的小常数更优；只有 n 超过 n₀ 后，渐近优势才显现。因此，当输入规模有限、常数差距巨大、或算法有缓存/内存局部性等实际开销时，应以内实测为准（profiling、benchmark）而非仅凭渐近界。工程上常用"小规模用简单算法、大规模用渐近高效算法"的混合策略（如 TimSort 对小数组用插入排序）。

渐近记号描述的是"极限行为"，而实际工程关注"给定输入规模下的真实时间"。常数因子、缓存命中、内存带宽、分支预测等都可能让渐近更优的算法在实际中更慢。故应结合理论复杂度与实测数据，在真实数据和目标规模上做基准测试。

• 渐近记号需要"趋于无穷"的语境
• 对具体 n 断言 O 的错误
• 平均情况的定义（输入分布）

渐近记号 O、Θ、Ω 定义在"存在 n₀ 使对所有 n≥n₀ 成立"的极限语境下，描述的是函数随 n 趋于无穷的增长率。因此不能对"具体输入规模 n=100"断言 O 界——O(n) 只说明存在某个常数 c 使 T(n)≤c·n 对足够大的 n 成立，而不给出 c 的具体值，也无法对单个 n 给出量化结论。对具体规模断言 O 是将其误当作"精确时间"或"绝对上界"。平均情况（average-case）的定义依赖输入分布：假设输入按某个概率分布（通常均匀分布）出现，平均复杂度 = 各输入下运行时间的期望值。例如快速排序的平均复杂度 = 对均匀随机排列的期望比较次数 = Θ(n log n)。平均情况与最坏情况、最好情况都可能不同，且平均情况的分布假设不同结论可能不同。

渐近记号是"关于 n 的函数的归类"，不是"某个 n 的绝对度量"。误用的常见形式是"n=100 时这是 O(n log n)"，正确的是"该算法的时间复杂度为 O(n log n)"。平均情况必须明确分布假设，否则无意义。

• 最坏、最好、平均的概念
• 期望复杂度（随机化）与平均复杂度的区别
• 快速排序三者的具体值

最坏复杂度：对"最不利输入"的复杂度上界。快速排序最坏情况发生在每次划分都极不平衡（如已排序输入且选首元素为 pivot），此时 T(n)=O(n) 每次划分，递推 T(n)=T(n−1)+O(n)，得 Θ(n²)。最好情况：pivot 每次恰好把数组分成两半，T(n)=2T(n/2)+O(n)=Θ(n log n)。平均复杂度（average-case）：假设输入均匀随机，快速排序期望比较次数为 Θ(n log n)，由递推或比较次数和推导。期望复杂度（expected）：对随机化算法，期望针对算法的随机选择（如随机 pivot），对任何输入都期望 Θ(n log n)（随机化快速排序）。三者区别：最坏是"输入决定"的保证，平均是"输入分布决定"的期望，期望是"随机化算法固有的随机性"的期望，随机化可将平均复杂度"推广"到任何输入。

快速排序的经典教训：最坏 Θ(n²)（输入不利）vs 平均 Θ(n log n)（输入均匀）vs 期望 Θ(n log n)（随机化）。随机化把"对输入分布的平均"升级为"对任何输入都期望"，从而消除病态输入的影响。

• 递归深度对栈空间的影响
• 递归深度作为复杂度分析的一部分
• 调用栈溢出与实现细节

对 f(n)=f(f(n-1)) 这类递归，其递归深度极大地影响实际运行。若 f(n) 的递归深度不是 O(log n) 而是 O(n) 或更深，则调用栈会占用 O(n) 空间，在 n 很大时可能栈溢出（Stack Overflow），导致算法无法实际运行。渐近分析常只报告时间复杂度而忽略空间/栈深度，但在工程中，递归深度（=调用栈层数）本身就是空间复杂度，且与具体实现（如 JVM 默认栈大小、栈帧大小）相关。因此对"递归深度很深"的算法，即使时间界是 O(n)，实际也可能因栈溢出而失败，需改为迭代或用显式栈、增大栈空间。此外 f(f(n-1)) 形式暗示"自我引用"，其值可能定义不明确或收敛极慢，需要先明确其定义域与终止条件，才会进入渐近分析。

这个问题的边界在于：渐近记法通常假设"无限栈/无限内存"，而真实递归受栈空间限制。递归深度 = 栈空间，是空间复杂度的一部分，应纳入分析。对深度 O(n) 的递归，实际通常不可行，需优化为尾递归或迭代。

• Stirling 公式 ln(n!) ≈ n ln n − n
• 取对数比较 2^n 与 n!
• 渐近阶的结论

n! 增长远快于 2^n。取对数比较：ln(n!) = n ln n − n + O(ln n)（Stirling），而 ln(2^n) = n ln 2。对足够大的 n，n ln n − n 远大于 n ln 2（因为 ln n 增长远超 ln 2+n 的常数项），故 ln(n!) ≫ ln(2^n)，即 n! ≫ 2^n。更严格地，n!/2^n = (n/2)((n−1)/2)·…·(1/2)，当某个因子超过 1 后迅速增长，n! 相对 2^n 的比值趋近 ∞。渐近阶上，n! = Θ(n^(n+1/2)/e^n)（Stirling 精确形式），而 2^n = e^(n ln 2)，两者比值 n!/2^n → ∞，故 n! = ω(2^n)。事实上 n! 比任何指数函数 2^(cn) 都快。

Stirling 公式把阶乘转为指数/幂形式，使取对数比较奏效：ln n! 的 n ln n 项主导，而 ln 2^n 只有线性项 n ln 2，故 n! 以超指数方式超过 2^n。这是比较"阶乘 vs 指数"的标准工具。

• O 记号只给渐近上界，非逐点绝对上界
• 常数因子与 n₀ 的存在
• 反例构造

该表述错误。O(n²) 的定义是：存在常数 c>0 和 n₀，使对所有 n≥n₀ 有 f(n)≤c·n²。它只保证"足够大的 n 之后 f 被 c·n² 界住"，并不要求 f(n)≤n² 对每个 n 都成立，也不排除在某个范围内 f 超过 n²。反例：f(n)=2n²，则 f(n)=O(n²)（取 c=2），但 f(n)=2n²>n² 对每个 n 恒成立，即 f 永远超过 n²。更极端的反例：f(n)=n²+1000n，f=O(n²)，但在 n 很小时 f 远大于 n²。故 O(n²) 只是"f 的增长率不超过 n² 的增长率"，不是"f≤n²"。

误区在于把渐近上界误读为逐点绝对上界。O 记号允许常数 c 和阈值 n₀，c 可以任意大，因此 f 可以以任意常数倍超过 n² 而仍满足 O(n²)。正确理解是"f 与 n² 同阶或更低"。

• 对数求和 ln(n!) = Σ ln k
• 用积分（上/下界）逼近求和的技巧
• 得到 n ln n − n

ln(n!) = Σ_{k=1}^n ln k。用积分近似：ln k 是单调递增函数，故对 k 有 ∫{k−1}^{k} ln x dx ≤ ln k ≤ ∫{k}^{k+1} ln x dx。求和得 ∫_0^n ln x dx ≤ Σ ln k ≤ ∫_1^{n+1} ln x dx。∫ ln x dx = x ln x − x。于是下界 ≈ n ln n − n + O(1)，上界 ≈ (n+1)ln(n+1) − (n+1) ≈ n ln n − n + O(ln n)。两端都给出 n ln n − n + O(ln n)，故 ln(n!) = n ln n − n + O(ln n)。取指数得 n! = e^(n ln n − n + O(ln n)) = (n/e)^n · n^O(1) = Θ((n/e)^n · √n)（用更精确的 Euler–Maclaurin 可得 n! ~ √(2πn)·(n/e)^n）。因此 n! 与 (n/e)^n 渐近等价（相差多项式 √n 因子）。

关键思想是"用积分逼近单调函数的求和"：ln k 单调使上下界积分都收敛到同一量级 n ln n − n。这是斯特林公式的入门级证明，更精确的 √(2πn) 因子需 Euler–Maclaurin 或 Laplace 方法，但核心对数形式 n ln n − n 已由积分逼近得出。

• O 的传递性证明
• Θ 的对称性（Θ 对称于 f=Θ(g)⟺g=Θ(f)）
• Θ 的自反性（f=Θ(f)）

传递性证明：f=O(g) 存在 c₁>0、n₁ 使 n≥n₁ 时 f(n)≤c₁·g(n)；g=O(h) 存在 c₂>0、n₂ 使 n≥n₂ 时 g(n)≤c₂·h(n)。取 n₀=max(n₁,n₂)，c=c₁·c₂，则对 n≥n₀：f(n)≤c₁·g(n)≤c₁·c₂·h(n)=c·h(n)，故 f=O(h)。O 是预序关系（满足传递性与自反性）。Θ 的对称性：f=Θ(g) 当且仅当存在 c₁,c₂>0 使 c₁·g(n)≤f(n)≤c₂·g(n)（n≥n₀），两边同除得 (1/c₂)·f(n)≤g(n)≤(1/c₁)·f(n)，故 g=Θ(f)，即 Θ 对称。Θ 的自反性：f=Θ(f) 显然成立（取 c₁=c₂=1）。故 Θ 是等价关系（自反、对称、传递）。

这些性质直接来自定义中的不等式链。O 关系的传递性通过"常数相乘、阈值取 max"实现；Θ 对称性由上下界互换得到，自反性 trivial。这些性质使我们能把算法按复杂度分为等价类。

• 五类记号的定义
• 极限比值判定法
• 各记号与极限的关系

严格定义（存在 c>0、n₀）：O(g)={f: 0≤f(n)≤c·g(n)，n≥n₀}；Ω(g)={f: f(n)≥c·g(n)≥0，n≥n₀}；Θ(g)={f: c₁·g(n)≤f(n)≤c₂·g(n)}；o(g)={f: 对任意 c>0 存在 n₀ 使 f(n)<c·g(n)，n≥n₀}（即 f/g→0）；ω(g)={f: 对任意 c>0 存在 n₀ 使 f(n)>c·g(n)}（即 f/g→∞）。极限比值法：设 L=lim f(n)/g(n)。若 L=0，则 f=o(g)（且 f=O(g)）；若 0<L<∞，则 f=Θ(g)（且 f=O(g)、f=Ω(g)）；若 L=∞，则 f=ω(g)（且 f=Ω(g)）；若 L 不存在或振荡，则极限比值法失效，需用定义判断。五种记号的关系：O 是上界，Ω 是下界，Θ 是上下界都有，o 是严格上界（排除同阶），ω 是严格下界。

极限比值法把渐近比较转化为极限计算，是判定最直接的手段。但要注意极限不存在时（如 f、g 振荡）不能滥用，需回归定义。五类记号完整覆盖"上界/下界/严格上界/严格下界/紧确界"。

• 常见函数的增长排序
• 证明方法：取对数、极限比值、Stirling
• 各函数之间的链式关系

从低到高排序：log n < √n < n < n log n < n² < 2ⁿ < n!。证明方法：①log n vs √n：令 k=log n，则 n=2^k，√n=2^(k/2)，比较 log n=k 与 2^(k/2)，后者增长更快，故 √n≫log n；或用极限比值 (log n)/√n→0。②n vs √n：n/√n=√n→∞，故 √n=o(n)。③n log n 略大于 n：比值 log n→∞。④n log n vs n²：n²/(n log n)=n/log n→∞，故 n log n=o(n²)。⑤n² vs 2ⁿ：取对数 2 ln n vs n ln 2，后者增长更快，故 2ⁿ≫n²。⑥2ⁿ vs n!：用 Stirling，n!~√(2πn)(n/e)^n，n!/2ⁿ→∞，故 n!≫2ⁿ。极限比值法（f/g→0 或 ∞）与取对数法是核心工具。

排序的证明核心是"取对数"与"极限比值"：对数函数换底后各项可以比较，Stirling 用于阶乘。这些函数构成算法分析的常用参照系，记住相对顺序即可快速定位算法的复杂度。

• 取对数把指数/幂比较转为线性比较
• 多项式 vs 指数、对数 vs 多项式
• 常数的处理

取对数法：比较 n^a 与 b^n（a>0、b>1）：两边取对数得 a·ln n 与 n·ln b。a·ln n 是 O(ln n)，n·ln b 是 Θ(n)，后者增长更快，故 b^n≫n^a（任何指数函数快于任何多项式）。比较 log n 与 n^ε（ε>0）：取对数得 ln ln n 与 ε·ln n，后者增长更快，故 n^ε≫log n（任何正幂多项式快于对数）。一般技巧：①对指数与幂、幂与对数的比较，取对数把指数降下来；②比较 log n 与 n^ε 可先令 n=2^k 或取对数；③对两个都含指数的函数，取对数后比较剩余部分。注意取对数比较是"单调变换"，保持原始大小关系，且对 ln 增长可以做数的比较。

取对数是处理"幂/指数/对数混合"的标准武器：把指数变成乘法、把乘法变成加法，把幂变成线性，从而简化为可比较的简单函数。记住两条铁律：指数>>多项式，多项式>>对数。

• o 的定义与极限的联系
• Θ 的定义与极限的联系
• 极限的 ε−δ 论证

证明 f=o(g)：设 lim f/g=0，则对任意 c>0，存在 n₀ 使所有 n≥n₀ 有 f(n)/g(n)<c，即 f(n)<c·g(n)。这正是 o 的定义（对任意 c>0 存在 n₀），故 f=o(g)。证明 f=Θ(g)：设 lim f/g=L，0<L<∞。取 ε=L/2，则由极限定义存在 n₀ 使 n≥n₀ 时 |f/g−L|<L/2，即 L/2 < f(n)/g(n) < 3L/2。令 c₁=L/2、c₂=3L/2，则 c₁·g(n)≤f(n)≤c₂·g(n)，这正是 Θ 的定义，故 f=Θ(g)。（需假设 g(n)>0 且足够大 n 时 f(n)≥0。）

极限比值法可直接翻译为 o 或 Θ 的定义条件：极限为 0 恰恰是"对任意 c 下界""可任意小"，极限为非零常数 L 则给出"上界 3L/2 与下界 L/2 两个常数"。这是极限与渐近记号之间最直接的桥梁。

• Θ 定义中找常数 c₁、c₂、n₀
• 上下界常数的选取
• 为何 c₁=c₂=1 不可行

设 f(n)=n²+3n+1。上界：f(n)≤n²+3n²+n²=5n²（对 n≥1，因 3n≤3n²、1≤n²），取 c₂=5、n₀=1 得 f(n)≤5n²，故 f=O(n²)。下界：f(n)≥n²，取 c₁=1 得 f(n)≥1·n²，故 f=Ω(n²)。综上 f=Θ(n²)。为何不能取 c₁=c₂=1：若 c₁=c₂=1，则要求 n²≤f(n)≤n² 对足够大 n 成立，即 f(n)=n² 恒成立，但 f(n)=n²+3n+1>n² 对每个 n 都成立，上界 n² 不满足（这是上界，不是下界）。实际上 c₁=1 是下界的合法选择（f≥n²），但 c₂=1 不成立（f>n²）。因此 c₁、c₂ 必须分别满足下界与上界，取 c₁=1、c₂=5 即可，不能都取 1。

Θ 要求找一个常数下界和一个常数上界，分别对应 f 与 n² 的比值下界与上界。f/n²=1+3/n+1/n²，其下界趋近 1（可取 c₁=1），上界是 5（n≥1 时）。若 c₁=c₂=1 等价于声称 f/n²≡1，显然错误，因为 f 严格大于 n²。

• 五种记号的形式化定义
• 各记号的"满足但不满足更强"的例子
• 区分 O/Θ、o/O、Ω/ω

形式化定义（存在 c>0、n₀）：

• O(g)：存在 c>0、n₀，使 n≥n₀ 时 0≤f(n)≤c·g(n)。
• Ω(g)：存在 c>0、n₀，使 n≥n₀ 时 0≤c·g(n)≤f(n)。
• Θ(g)：存在 c₁,c₂>0、n₀，使 n≥n₀ 时 c₁·g(n)≤f(n)≤c₂·g(n)。
• o(g)：对任意 c>0 存在 n₀，使 n≥n₀ 时 0≤f(n)<c·g(n)。
• ω(g)：对任意 c>0 存在 n₀，使 n≥n₀ 时 0≤c·g(n)<f(n)。 例子（满足但不满足更强）：O：f(n)=n、g(n)=n，f=O(g) 但 f≠o(g)（比值 f/g=1 不趋于 0）。Ω：f(n)=n、g(n)=n，f=Ω(g) 但 f≠ω(g)（比值 1 不趋于无穷）。Θ：f(n)=n²+1、g(n)=n²，f=Θ(g) 但 f 不等于 g（n≥1 时）。o：f(n)=n、g(n)=n²，f=o(g) 但 f≠Θ(g)（比值 1/n→0）。ω：f(n)=n²、g(n)=n，f=ω(g) 但 f≠Θ(g)（比值 n→∞）。

五种记号形成"上界/下界/紧确/严格上界/严格下界"的完整体系。区分它们的关键是"常数 c 是否任意"（O/Ω 存在某个 c，o/ω 对任意 c）。"满足但不满足更强"的例子用于检验对记号强弱关系的理解——例如 f=g 时 f=O(g) 但 f≠o(g)。

• 取对数处理幂的幂
• 比较 log n·log n 与 n·log(log n)
• 渐近大小结论

记 A=n^(log n)、B=(log n)^n。取对数：ln A = log n · ln n = (log n)(ln n) = (ln n/ln 2)(ln n) = Θ((ln n)²)。ln B = n · ln(log n)。比较 (ln n)² 与 n·ln(log n)：前者是 (ln n)²，后者是线性 n 乘 ln(log n)。对足够大的 n，n·ln(log n) 增长远超 (ln n)²（因为 n 是线性、ln(log n) 是缓慢增长但 n 主导）。故 ln B ≫ ln A，即 B ≫ A，所以 (log n)^n 增长快于 n^(log n)。更精确地，ln B/ln A = n·ln(log n)/((ln n)²) → ∞，故 (log n)^n = ω(n^(log n))。

两个都是"幂的幂"，取对数后变成"log n × log n"与"n × log(log n)"的乘积比较。关键判断是 n 线性项主导 (ln n)²，故 B 更大。取对数把乘法比较转为线性 vs 二次对数比较，使结论清晰。