算法复杂度完全指南时间复杂度、渐近符号与主定理OI-wiki 基础篇【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读时间复杂度和空间复杂度是衡量一个算法效率的重要标准也是算法竞赛OI/ICPC中判断一个解法能否通过数据范围的核心依据。本文基于 OI-wiki 基础算法章节的复杂度文档展开系统讲解基本操作数、时间复杂度的定义、五种渐近符号、主定理Master Theorem以及空间复杂度等内容并结合本仓库中排序、搜索等具体算法的复杂度结论帮助你建立一套看到代码就能估算复杂度、看到复杂度就能判断可行性的实战能力。基本操作数衡量算法效率的起点同一个算法在不同的计算机上运行的速度会有一定的差别并且实际运行速度难以在理论上进行计算实际去测量又比较麻烦。因此我们通常考虑的不是算法运行的实际用时而是算法运行所需要进行的基本操作的数量。在普通的计算机上以下操作都可以看作基本操作加减乘除等算术运算访问变量基本数据类型的变量给变量赋值。对基本操作的计数或是估测可以作为评判算法用时的指标。正是因为用基本操作数代替实际用时复杂度分析才能摆脱硬件差异在理论上被统一讨论。时间复杂度定义衡量一个算法的快慢一定要考虑数据规模的大小。所谓数据规模一般指输入的数字个数输入中给出的图的点数与边数其他与问题规模相关的量。一般来说数据规模越大算法的用时就越长。而在算法竞赛中衡量一个算法的效率时最重要的不是看它在某个数据规模下的用时而是看它的用时随数据规模而增长的趋势即时间复杂度。为什么只看增长趋势考虑用时随数据规模变化的趋势主要有以下几点原因数据规模通常很大。现代计算机每秒可以处理数亿乃至更多次基本运算因此我们处理的数据规模通常很大。如果算法 A 在规模为 $n$ 的数据上用时为 $100n$而算法 B 在规模为 $n$ 的数据上用时为 $n^2$在数据规模小于 $100$ 时算法 B 用时更短但在一秒钟内算法 A 可以处理数百万规模的数据而算法 B 只能处理数万规模的数据。在允许算法执行时间更久时时间复杂度对可处理数据规模的影响就会更加明显远大于同一数据规模下用时的影响。消除基本操作间用时的差异。我们采用基本操作数来表示算法的用时而不同的基本操作实际用时是不同的例如加减法的用时远小于除法的用时。计算时间复杂度而忽略不同基本操作之间的区别、以及一次基本操作与十次基本操作之间的区别可以消除基本操作间用时不同的影响。最坏时间复杂度与平均时间复杂度算法的运行用时并非完全由输入规模决定而是也与输入的内容相关。所以时间复杂度又分为几种最坏时间复杂度每个输入规模下用时最长的输入对应的时间复杂度。在算法竞赛中由于输入可以在给定的数据范围内任意给定为保证算法能够通过某个数据范围内的任何数据一般考虑最坏时间复杂度。平均期望时间复杂度每个输入规模下所有可能输入对应用时的平均值随机输入下期望用时的复杂度。OI-wiki 基础章节同样沿用了这一划分。例如在排序简介中明确指出时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度OI 竞赛中要考虑的一般是最坏时间复杂度因为它代表的是算法运行水平的下界在评测中不会出现更差的结果。本仓库各排序页面也都给出了这三类复杂度的具体数值例如冒泡排序在序列完全有序时只需遍历一遍数组最优时间复杂度为 $O(n)$最坏情况下要执行 $\frac{(n-1)n}{2}$ 次交换操作最坏时间复杂度为 $O(n^2)$。所谓用时随数据规模而增长的趋势是一个模糊的概念我们需要借助下文所介绍的渐近符号来形式化地表示时间复杂度。渐近符号的定义渐近符号是函数的阶的规范描述。简单来说渐近符号忽略了一个函数中增长较慢的部分以及各项的系数在时间复杂度相关分析中系数一般被称作「常数」而保留了可以用来表明该函数增长趋势的重要部分。一个简单的记忆方法是含等于非严格用大写不含等于严格用小写相等是 $\Theta$小于是 $O$大于是 $\Omega$。大 $O$ 和小 $o$ 原本是希腊字母 Omicron由于字形相同也可以理解为拉丁字母的大 $O$ 和小 $o$。在英文中词根「-micro-」和「-mega-」常用于表示 10 的负六次方百万分之一和六次方百万也表示「小」和「大」小和大也正是希腊字母 Omicron 和 Omega 常表示的含义。大 Θ 符号对于函数 $f(n)$ 和 $g(n)$$f(n)\Theta(g(n))$当且仅当 $\exists c_1,c_2,n_00$使得 $\forall n \ge n_0, 0\le c_1\cdot g(n)\le f(n) \le c_2\cdot g(n)$。也就是说如果函数 $f(n)\Theta(g(n))$那么我们能找到两个正数 $c_1, c_2$使得 $f(n)$ 被 $c_1\cdot g(n)$ 和 $c_2\cdot g(n)$ 夹在中间。例如$3n^25n-3\Theta(n^2)$这里的 $c_1, c_2, n_0$ 可以分别是 $2, 4, 100$$n\sqrt{n}n\log^5 nm\log mnm\Theta(n\sqrt{n}m\log mnm)$这里的 $c_1, c_2, n_0$ 可以分别是 $1, 2, 100$。大 O 符号$\Theta$ 符号同时给了我们一个函数的上下界。如果只知道一个函数的渐近上界而不知道其渐近下界可以使用 $O$ 符号。$f(n)O(g(n))$当且仅当 $\exists c,n_0$使得 $\forall n \ge n_0, 0\le f(n)\le c\cdot g(n)$。研究时间复杂度时通常会使用 $O$ 符号因为我们关注的通常是程序用时的上界而不关心其用时的下界。需要注意这里的「上界」和「下界」是对于函数的变化趋势而言的而不是对算法而言的。算法用时的上界对应的是「最坏时间复杂度」而非大 $O$ 记号。所以使用 $\Theta$ 记号表示最坏时间复杂度是完全可行的甚至可以说 $\Theta$ 比 $O$ 更加精确。而使用 $O$ 记号的主要原因一是我们有时只能证明时间复杂度的上界而无法证明其下界这种情况一般出现在较为复杂的算法以及复杂度分析中二是 $O$ 在电脑上输入更方便一些。大 Ω 符号同样的我们使用 $\Omega$ 符号来描述一个函数的渐近下界。$f(n)\Omega(g(n))$当且仅当 $\exists c,n_0$使得 $\forall n \ge n_0, 0\le c\cdot g(n)\le f(n)$。小 o 符号如果说 $O$ 符号相当于小于等于号那么 $o$ 符号就相当于小于号。小 $o$ 符号大量应用于数学分析中函数在某点处的泰勒展开式拥有皮亚诺余项使用小 $o$ 符号表示严格小于从而进行等价无穷小的渐近分析。$f(n)o(g(n))$当且仅当对于任意给定的正数 $c$$\exists n_0$使得 $\forall n \ge n_0, 0\le f(n) c\cdot g(n)$。小 ω 符号如果说 $\Omega$ 符号相当于大于等于号那么 $\omega$ 符号就相当于大于号。$f(n)\omega(g(n))$当且仅当对于任意给定的正数 $c$$\exists n_0$使得 $\forall n \ge n_0, 0\le c\cdot g(n) f(n)$。下图直观展示了 $\Theta$、$O$、$\Omega$ 三种符号的几何含义子图 (a) 中 $f(n)$ 被 $c_1 g(n)$ 与 $c_2 g(n)$ 两条虚线夹在中间对应 $\Theta(g(n))$子图 (b) 中 $f(n)$ 始终位于 $c g(n)$ 下方对应 $O(g(n))$子图 (c) 中 $f(n)$ 始终位于 $c g(n)$ 上方对应 $\Omega(g(n))$。三个子图都以 $n_0$ 为分界强调渐近关系只在 $n$ 足够大之后成立。常见性质$f(n) \Theta(g(n))\iff f(n)O(g(n))\land f(n)\Omega(g(n))$$f_1(n) f_2(n) O(\max(f_1(n), f_2(n)))$$f_1(n) \times f_2(n) O(f_1(n) \times f_2(n))$$\forall a \neq 1, \log_a{n} O(\log_2 n)$。由换底公式可以得知任何对数函数无论底数为何都具有相同的增长率因此渐近时间复杂度中对数的底数一般省略不写。简单的时间复杂度计算的例子三层for循环下面这段代码在 C、Python、Java 三种语言中的写法如下 Ccpp int n, m; std::cin n m; for (int i 0; i n; i) { for (int j 0; j n; j) { for (int k 0; k m; k) { std::cout hello world\n; } } } Pythonpython n int(input()) m int(input()) for i in range(0, n): for j in range(0, n): for k in range(0, m): print(hello world) Javajava int n, m; n input.nextInt(); m input.nextInt(); for (int i 0; i n; i) { for (int j 0; j n; j) { for (int k 0; k m; k) { System.out.println(hello world); } } }如果以输入的数值 $n$ 和 $m$ 的大小作为数据规模则上面这段代码的时间复杂度为 $\Theta(n^2m)$——因为最内层语句总共被执行 $n \times n \times m$ 次。这一数循环层数来近似估计复杂度的做法在排序简介中也被作为快速估算手段介绍。DFS在对一张 $n$ 个点 $m$ 条边的图进行 DFS 时由于每个节点和每条边都只会被访问常数次复杂度为 $\Theta(nm)$。值得注意的是DFS 页面对此还补充了更细致的适用前提该算法通常的时间复杂度为 $O(nm)$、空间复杂度为 $O(n)$其中栈空间的空间复杂度也是 $O(n)$但只有在平均 $O(1)$ 遍历一条边的条件下才能达到此时间复杂度例如用前向星或邻接表存储图如果用邻接矩阵则不一定能达到此复杂度。这也提醒我们复杂度的结论总是依附于具体的数据结构与实现方式。哪些量是常量当我们要进行若干次操作时如何判断这若干次操作是否影响时间复杂度呢例如 Ccpp constexpr int N 100000; for (int i 0; i N; i) { std::cout hello world\n; } Pythonpython N 100000 for i in range(0, N): print(hello world) Javajava final int N 100000; for (int i 0; i N; i) { System.out.println(hello world); }如果 $N$ 的大小不被看作输入规模那么这段代码的时间复杂度就是 $O(1)$。进行时间复杂度计算时哪些变量被视作输入规模是很重要的而所有和输入规模无关的量都被视作常量计算复杂度时可当作 $1$ 来处理。需要注意在进行时间复杂度相关的理论性讨论时「算法能够解决任何规模的问题」是一个基本假设当然在实际中由于时间和存储空间有限无法解决规模过大的问题。因此能在常量时间内解决数据规模有限的问题例如对于数据范围内的每个可能输入预先计算出答案并不能使一个算法的时间复杂度变为 $O(1)$。主定理Master Theorem对于递归算法我们可以使用 Master Theorem 来快速求得其复杂度。Master Theorem 递推关系式如下$$ T(n) a T\left(\frac{n}{b}\right)f(n)\qquad \forall n b $$那么$$ T(n) \begin{cases}\Theta(n^{\log_b a}) f(n) O(n^{\log_b (a)-\epsilon}),\epsilon 0 \ \Theta(f(n)) f(n) \Omega(n^{\log_b (a)\epsilon}),\epsilon\ge 0\ \Theta(n^{\log_b a}\log^{k1} n) f(n)\Theta(n^{\log_b a}\log^k n),k\ge 0 \end{cases} $$三种情况分别可以概括为情况一若 $f(n)$ 的增长率严格慢于 $n^{\log_b a}$则 $T(n)\Theta(n^{\log_b a})$整体复杂度由递归树叶子层的规模主导情况二若 $f(n)$ 的增长率严格快于 $n^{\log_b a}$则 $T(n)\Theta(f(n))$整体复杂度由每层合并的开销主导情况三若 $f(n)$ 与 $n^{\log_b a}$ 同阶允许相差 $\log^k n$ 因子则 $T(n)\Theta(n^{\log_b a}\log^{k1} n)$。需要注意的是这里的第二种情况还需要满足regularity condition正则条件即 $a f(n/b) \leq c f(n)$其中 $c$ 为某个小于 $1$ 的常数且 $n$ 充分大。证明思路与完整证明证明思路是将规模为 $n$ 的问题分解为 $a$ 个规模为 $\left(\frac{n}{b}\right)$ 的子问题然后依次合并直到合并到最高层。每一次合并子问题都需要花费 $f(n)$ 的时间。依据上述证明思路具体证明过程如下对于第 $0$ 层最高层合并子问题需要花费 $f(n)$ 的时间对于第 $1$ 层第一次划分出来的子问题共有 $a$ 个子问题每个子问题合并需要花费 $f\left(\frac{n}{b}\right)$ 的时间所以合并总共要花费 $a f\left(\frac{n}{b}\right)$ 的时间层层递推我们可以写出如下的递归树该图给出了递归树的结构与各层的合并开销这棵树的高度为 $\log_b n$共有 $n^{\log_b a}$ 个叶子从而$$ T(n) \Theta(n^{\log_b a}) g(n)其中 g(n) \sum_{j 0}^{\log_{b}{n - 1}} a^{j} f(n / b^{j}) $$接下来分三种情况讨论 $g(n)$第一种情况$f(n) O(n^{\log_b a-\epsilon})$因此 $g(n) O(n^{\log_b a})$第二种情况首先 $g(n) \Omega(f(n))$又因为 $a f\left(\dfrac{n}{b}\right) \leq c f(n)$只要 $c$ 的取值是一个足够小的正数、且 $n$ 的取值足够大就可以推导出 $g(n) O(f(n))$。两侧夹逼可以得出 $g(n) \Theta(f(n))$第三种情况$f(n) \Theta(n^{\log_b a})$因此 $g(n) O(n^{\log_b a} \log n)$$T(n)$ 的结果可在 $g(n)$ 得出后显然得到。主定理的应用示例下面举几个例子来说明主定理如何使用。$T(n) 2T\left(\frac{n}{2}\right) 1$那么 $a2, b2, \log_2 2 1$$\epsilon$ 可以取值在 $(0, 1]$ 之间从而满足第一种情况所以 $T(n) \Theta(n)$。这对应着归并排序每层 $O(1)$ 合并开销时的复杂度形态$T(n) T\left(\frac{n}{2}\right) n$那么 $a1, b2, \log_2 1 0$$\epsilon$ 可以取值在 $(0, 1]$ 之间从而满足第二种情况所以 $T(n) \Theta(n)$$T(n) T\left(\frac{n}{2}\right) \log n$那么 $a1, b2, \log_2 1 0$$k$ 可以取值为 $1$从而满足第三种情况所以 $T(n) \Theta(\log^2 n)$$T(n) T\left(\frac{n}{2}\right) 1$那么 $a1, b2, \log_2 1 0$$k$ 可以取值为 $0$从而满足第三种情况所以 $T(n) \Theta(\log n)$。主定理在本仓库的众多分治算法分析中都有实际对应。例如归并排序基于分治思想将数组分段排序后合并其时间复杂度在最优、最坏与平均情况下均为 $\Theta(n\log n)$——这正是 $T(n)2T(n/2)O(n)$ 满足主定理第二种情况$n^{\log_2 2}n$ 与 $f(n)n$ 同阶、$k0$的直接结论。均摊复杂度对于某些数据结构单次操作的开销可能波动很大例如一次扩容可能很贵此时需要用均摊复杂度来衡量一系列操作的平均代价。详情可见均摊复杂度该页面给出了完整的引入与三种分析方法聚合分析计算 $n$ 次操作的总成本再平均例如动态数组扩容$n$ 次插入总成本为 $O(n)$均摊到每次为 $O(1)$记账分析为低成本操作预存费用以支付未来的高成本操作例如为每次插入分配均摊成本 $3$$1$ 用于当前插入$2$ 预留给扩容势能分析定义满足初始势能为 $0$、任意状态势能非负的势能函数 $\Phi$令均摊成本 $\hat{c}c\Phi(S)-\Phi(S)$从而把总实际开销 $\sum c_i$ 控制在 $\sum p_i$ 之内。此外该页面还以堆栈的push/pop/multi-pop三种操作组合为例用三种方法分别证明了所有操作均摊成本为 $O(1)$。均摊分析不涉及概率它保证的是最坏情况下操作序列的平均成本。空间复杂度类似地算法所使用的空间随输入规模变化的趋势可以用空间复杂度来衡量。空间复杂度同样使用渐近符号描述并且同样需要先明确哪些量算作输入规模——与输入规模无关的额外空间如固定大小的临时数组视为常量。本仓库中有不少直观的例子例如二分查找中迭代版本的空间复杂度为 $O(1)$而递归无尾调用消除版本由于递归栈会占用 $O(\log n)$ 的空间再如 DFS 页面特别指出其空间复杂度 $O(n)$ 中包含了栈空间。这些例子说明空间复杂度的分析必须把递归栈、存储结构等隐性开销一并纳入。计算复杂性从算法分析走向理论本文主要从算法分析的角度对复杂度进行了介绍。如果对更深入的层次感兴趣可以在计算复杂性中进行更深入的了解该页面以图灵机为计算模型介绍了判定问题、可计算性、停机问题以及 $\mathsf{P}$、$\mathsf{NP}$、$\mathsf{NP}$-hard、$\mathsf{NP}$-complete、$\mathsf{PSPACE}$ 等复杂度类与谱系定理之间的关系。需要注意的是该页面明确指出这部分内容在 OI 中作用不大但遇到 NP-hard 问题时你可以据此判断它不存在多项式复杂度的解法。本仓库中的复杂度速查资源OI-wiki 基础章节的每一篇算法页面都给出了对应算法的时间/空间复杂度结论可作为本文的延伸练习素材排序简介基于比较的排序算法时间复杂度下限是 $O(n\log n)$而非比较的计数排序时间复杂度为 $O(nw)$其中 $w$ 代表输入数据的值域大小冒泡排序最优 $O(n)$、平均与最坏 $O(n^2)$归并排序三种情况下均为 $\Theta(n\log n)$空间复杂度 $\Theta(n)$二分查找最优时间复杂度 $O(1)$迭代/递归版本空间复杂度分别为 $O(1)$ 与 $O(\log n)$贪心以任务调度为例演示了排序 $O(n\log n)$ 堆维护 $O(n\log n)$的完整复杂度推导过程DFS$O(nm)$ 的前提是使用前向星或邻接表等 $O(1)$ 遍历一条边的图存储方式。这些页面在 docs/basic 目录下还配套了可运行的多语言代码docs/basic/code与输入输出样例docs/basic/examples在阅读复杂度结论的同时可以直接运行验证。掌握了本文的渐近符号与主定理之后再阅读这些页面的复杂度结论就会水到渠成。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考