Blog

本教程按“定义→基础计数→循环求和→对数结构→主定理及推广→迭代与递归→平均分析与摊还分析”的顺序展开，旨在帮助读者建立从直观计数到形式化求解、再到序列视角的完整复杂度分析框架，并给出面对具体算法时选择分析工具的依据。 一、什么是算法复杂度？ 1.1 从程序到运行时间函数 先约定记号。算法 \(A\) 的输入记作 \(x\)，输入规模记作 \(\lvert x\rvert=n\)；它在输入 \(x\) 上做的基本操作数，或者在某个计算模型下花的时间，记成 \(T_A(x)\)。 同一规模下输入千差万别，最坏情况自然取其中最贵的一个： \[ T_A(n)=\max_{\lvert x\rvert=n}T_A(x). \] 数组算法的规模一般就是元素个数，图算法的规模往往要同时看顶点数 \(V\) 和边数 \(E\)。规模怎么取，结论的含义就跟着变，这件事后面还会反复出现。 复杂度分析并不打算算出一台机器上的纳秒数——换台机器数字就变了。它只关心 \(n\) 越来越大时，成本以什么速度往上走。 比如某段程序的基本操作数是 \[ T(n)=3n^2+5n+7. \] \(n\) 还小的时候，平方项、一次项、常数项都还有存在感；\(n\) 到了几万，平方项就把另外两项压得看不见了。所以 \(T(n)=\Theta(n^2)\)。这里的等号不是说操作数真的等于 \(n^2\)，而是说增长速度和 \(n^2\) 只差一个常数倍。 1.2 三种渐近记号 约定 \(f(n)\)、\(g(n)\) 在 \(n\) 足够大时非负。 大 O 管上界。 \(f(n)=O(g(n))\) 的意思是：存在常数 \(c>0\) 和 \(n_0\)，从 \(n_0\) 往后一直有 \[ f(n)\le c,g(n). \] 换句话说，\(f\) 再怎么长，也长不过 \(g\) 的某个常数倍。 大 Ω 管下界。 \(f(n)=\Omega(g(n))\) 的意思是：存在常数 \(c>0\) 和 \(n_0\)，当 \(n\ge n_0\) 时 \[ f(n)\ge c,g(n). \] 大 Θ 是两侧都管。 \(f(n)=\Theta(g(n))\) 当且仅当 \(f(n)=O(g(n))\) 和 \(f(n)=\Omega(g(n))\) 同时成立，也就是 \(f\) 和 \(g\) 在常数因子意义下同阶。 拿 \(3n^2+5n+7\) 来说，它是 \(\Theta(n^2)\)，也是 \(O(n^3)\)，也是 \(\Omega(n^2)\)，但不是 \(\Theta(n^3)\)。说它 \(O(n^3)\) 并没有错，只是丢掉了一些信息，听起来像是我们不知道它其实只有平方那么快。 所以，能给出 \(\Theta\) 就别停在 \(O\)。如果只证出了单侧，写清楚是上界还是下界，比含糊地写一个 \(O\) 要好。 1.3 常见增长速度 增长速度从慢到快排一排： \[ 1\prec\log n\prec n\prec n\log n\prec n^2\prec n^3\prec c^n\prec n!, \] \(c>1\) 是常数，\(\prec\) 读作“比……长得慢”。这张表值得记熟，比较两个算法时，多数时候只是在表上比位置。 ...