渐近分析

概述

渐近分析 研究当输入规模 $n$ 趋于无穷大时，算法运行时间（或空间）的增长行为，忽略常数因子和低阶项。

定义

渐近分析

通过数学工具刻画函数 $T(n)$ 当 $n\to \infty$ 时的增长速率，使用 渐近记号（$O$, $\Omega$, $\Theta$, $o$, $\omega$）来描述算法资源消耗的本质特征。

核心性质

• 忽略常数因子：$3n^2$ 与 $100n^2$ 的渐近行为相同，均为 $\Theta (n^2)$。
• 忽略低阶项：$n^2+100n+1000=\Theta (n^2)$。
• 渐近分析关注的是增长趋势，适合比较不同算法在大规模输入下的相对性能。
• 对于小规模输入，常数因子和低阶项可能实际更重要，渐近分析不适用于此场景。

章节扩展

第1章：算法在计算中的角色

• 1.2 算法作为一种技术 中通过比较 $\Theta (n^2)$ 的插入排序与 $\Theta (n\lg n)$ 的归并排序，直观展示渐近分析的价值。

参见

• 渐近记号
• 大O记号
• 大Theta记号
• 算法效率