这里我们来聊聊算法以及它的效率问题。算法（Algorithm）是一套解决问题的明确步骤，可以看作是一组清晰且简单的指令集合（Weiss, 2014）1。从本质上讲，算法是一种定义明确的计算过程，它接受一个或多个输入值，并在有限的时间内生成对应的输出，其核心任务是将输入转化为输出（Cormen et al., 2022）2。
一个算法通常需要满足有穷性、确定性和可行性等基本特征，满足这些特征的算法可以被称为“能用”。然而，仅仅具备“能用”的属性显然还不够。如果一个算法需要耗费一年的时间来完成计算，它的实际意义就大打折扣；同样，如果算法的内存消耗巨大，超出了普通计算机的处理能力，它也无法广泛应用。因此，在设计和选择算法时，效率（Efficiency）成为一个不可忽视的核心因素。这其中，运行时间（Time Complexity）和内存消耗（Space Complexity）是衡量算法效率的两大关键指标。
基于此，我们不禁要思考：如何估算一个算法的运行时间？如何科学地衡量算法的效率？又如何通过优化，让算法的运行时间从几天甚至几年缩短到几秒？接下来的内容将围绕这些问题展开，希望能够提供一个直观的算法效率分析入门，同时也期待通过学习，咱们能够掌握选择和改进算法的基础方法，让程序运行得更快、更节省资源！
随机存取机模型（Random-access machine， RAM）
算法分析本质上是比较不同算法的效率问题，而要公平比较，必须有一个理论上的对比基准（Comparison Baseline），也就是得有一把“统一的尺子”。这时候，随机存取机（Random-access machine, RAM）模型就闪亮登场了，它提供了一个理想化的计算环境，帮助我们统一衡量算法的效率。
可以把 RAM 模型想象成一台虚拟的“完美计算机”：这台计算机的操作规则非常简单——每条指令（Instruction）按顺序执行（Sequential Execution），不存在任何并发操作（Concurrent Operation）（Cormen et al., 2022）2。不管是执行加法、减法、赋值，还是从数组中读取数据，每个基本操作的成本（无论是时间还是存储空间）都被假定为相同。不仅如此，RAM 模型假设内存是无限的，访问任何位置都只需要一眨眼，不管你取的是第一个位置，还是第十亿个位置，速度都一样快。没有缓存，没有硬盘，更没有网络延迟，就是个“理想世界”。
在这个“理想世界”中，我们能专注于算法本身，不用考虑各种硬件细节。就比如说，如果我们想比较两个算法的运行速度，一个用了一百万次加法，一个用了五十万次加法和五十万次数组访问，在 RAM 模型里它们的时间是差不多的，因为每个操作的时间都是一样的。可以说，RAM 模型为我们分析算法提供了一个公平的对比平台。我们可以简单直观地分析不同算法的效率，比较谁的时间复杂度更低，谁的增长速度更慢。
当然，RAM 模型也似乎有点“理想化过头”。在现实中，即使在同一机器上，不同的指令执行时间差别也很大，像排序、求幂这种操作可能需要更长时间。此外，RAM 模型完全忽略了现代计算机的内存层次结构，比如缓存和内存之间的速度差异，或者硬盘访问的延迟等。而这些在真实运行中往往对算法的性能影响很大。尽管 RAM 模型无法反映所有的现实细节，它仍然是一个非常有用的工具。因为它让我们抓住了算法分析的核心，提供了一把“统一的尺子”，用来衡量算法优劣，也即，在同一个理想化环境下，为不同算法制定统一的衡量尺度。
怎么分析？
在 RAM 模型的“理想世界”里，我们先不必过多考虑空间上的约束（因为它假设有无限可用的内存空间），可以专注于时间方面的分析。由于该模型也假设算法的每条指令均按顺序执行且运行每条指令的时间成本一致（比如 $c$ 个单位时间），这也就意味着，我们可以统计一个算法在运行过程中所有指令的运行次数，以此作为衡量这个算法的效率指标。
1def insertion_sort(arr):
2 """
3 对列表 arr 进行插入排序
4 """
5 # 从第二个元素(下标 1)开始向前比较插入
6 for i in range(1, len(arr)):
7 # 取出当前需要插入的元素
8 key = arr[i]
9 j = i - 1
10
11 # 在已经排序好的序列中，从后往前遍历
12 # 如果前面的元素比 key 大，就把它往后挪
13 while j >= 0 and arr[j] > key:
14 arr[j + 1] = arr[j]
15 j -= 1
16
17 # 找到合适的位置后，将 key 插入
18 arr[j + 1] = key
19
20 return arr
insertion_sort() 函数的功能是对给定的列表 list 实例进行插入排序。其基本思想是将列表分为两个部分：已排序部分和未排序部分，初始时已排序部分仅包含列表的第一个元素，然后从未排序部分逐一取出元素，依次插入到已排序部分的适当位置，直到整个列表都变为有序。在 insertion_sort 函数中，外层循环遍历未排序部分的每一个元素，而内层循环则用于将当前元素插入到已排序部分的合适位置。为了完成这一过程，内层循环会逐个比较当前元素与已排序部分中元素的大小，并根据需要进行位置交换。下图动态展示了其基本过程：
现在我们基于 RAM 模型来分析，当一个长度为 $n$ 的列表 arr 被输入到 insertion_sort() 函数中时，核心语句（也即上面代码块中用灰色颜色标记的代码）的执行的总成本时多少？
首先，我们分析下第 6 行代码（for i in range(1, len(arr)）。这是一条循环控制语句，用于从列表的索引 1 开始遍历到索引 $n−1$，共遍历 $n−1$ 次。因此，第 6 行代码的执行总次数为 $n−1$。假设每次循环的执行成本是一个固定值 $c_6$，那么，执行第 6 行代码的总成本可以表示为 $c_6 \times (n-1)$。
其次，关于第 8-9 以及第 18 行代码，由于这些语句主要涉及基本的赋值和算术计算，每次执行的成本分别为单位成本 $c_8$，$c_9$，$c_{18}$。由于这些语句位于外层 for 循环内，它们将被执行 $n−1$ 次，因此它们的总成本为：$(c_8 + c_9 + c_{18})\times (n-1)$
最后，我们分析第 13-15 行代码所在的 while 循环。这部分代码的执行次数的确定有点麻烦，我们并不能够很直观地观察出它到底会执行多少次。主要是由于这部分代码的执行次数很大程度上取决于 arr[j] > key 的判断条件。而这个又取决于输入列表的排序状态。当输入列表已经是严格升序排列时，while 循环的判断条件 arr[j] > key 总是第一次比较就失败，因此 while 循环仅执行 1 次。在此情况下，while 循环体也不会被执行。同上，考虑到该语句位于外层 for 循环内，因此第 13-15 行代码执行总成本可以表示为 $c_{13} \times (n-1)$。当输入列表已经是严格降序排列时，那么while 循环的判断条件 arr[j] > key 的结果总是真（True），直到比较到已排序部分的最前端。这也意味着，原始列表中的第 2 个元素需要执行 1 次比较，第 3 个元素需要执行 2 次比较，$\ldots$，第 $n$ 个元素需要执行 $n - 1$ 次比较。所以说，while 循环的执行次数总和为 $\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2}$。因此，在此情景下，第 13-15 行的执行总成本可是表示为 $(c_{13} + c_{14} + c_{15}) \times \frac{(n-1)n}{2}$。
除了这两种极端情况外，更为一般的是输入序列的排序状态是一个随机排列。在随机排列的情况下，我们无法直接得出 while 循环的执行次数，因为它依赖于 arr[j] > key 判断条件的概率分布，而这又与输入列表的初始排列状态密切相关。因此，为了分析第 13-15 行代码的执行次数，我们需要借助概率分析（Probabilistic Analysis）方法。假设输入列表是一个均匀随机排列（Uniformly Random Permutation），对于每个元素 arr[i] 来说，它在已排序部分中的最终位置是均匀分布的。这意味着，在插入排序中，当处理第 $i$ 个元素时，它平均需要比较到已排序部分的一半位置。这也可以理解为，每次插入操作需要执行约 $\frac{i}{2}$ 次比较。因此，原始列表中的第 2 个元素平均需要执行 $\frac{1}{2}$ 次比较，第 3 个元素平均需要执行 $\frac{2}{2}$ 次比较，$\ldots$，第 $n$ 个元素平均需要执行 $\frac{(n - 1)}{2}$ 次比较。将所有元素的平均比较次数相加，while 循环的平均执行次数总和为 $\sum_{i=1}^{n-1} \frac{i}{2} = \frac{(n-1)n}{4}$。因此，在随机排列的情况下，第 13-15 行代码的总执行成本可以表示为：$(c_{13} + c_{14} + c_{15}) \times \frac{(n-1)n}{4}$。
因此，整个插入排序算法的总成本我们可以分为三种情况：
第一种情况是输入列表已经是严格升序排列，此时的总成本为：
$$ T_{\text{best}}(n) = c_6 \times (n-1) + (c_8 + c_9 + c_{18})\times (n-1) + c_{13} \times (n-1) = a \times n + b $$其中 $ a = c_6 + c_8 + c_9 + c_{18} + c_{13} $，$b = -(c_6 + c_8 + c_9 + c_{18} + c_{13})$。可以看出，此种情况下，插入排序算法的时间开销 ($T(n)$) 与输入列表的大小 $n$ 成线性关系。
第二种情况是输入列表已经是严格降序排列，此时的总成本为：
$$ \eqalign{ T_{\text{worst}}(n) &= c_6 \times (n-1) + (c_8 + c_9 + c_{18}) \times (n-1) + (c_{13} + c_{14} + c_{15}) \times \frac{(n-1)n}{2} \cr &= \frac{(c_{13} + c_{14} + c_{15})}{2} \times n^2 + (c_6 + c_8 + c_9 + c_{18} - \frac{(c_{13} + c_{14} + c_{15})}{2}) \times n \cr &\quad - (c_6 + c_8 + c_9 + c_{18}) \cr &= a \times n^2 + b \times n + c } $$其中 $a = \frac{(c_{13} + c_{14} + c_{15})}{2}$， $b = (c_6 + c_8 + c_9 + c_{18} - \frac{(c_{13} + c_{14} + c_{15})}{2})$，$c = - (c_6 + c_8 + c_9 + c_{18}) $。可以看出，此种情况下，插入排序算法的时间开销 ($T(n)$) 与输入列表的大小 $n$ 成多项式关系，且最高次为二次。
第三种情况是输入列表随机排列，此时的总成本为：
$$ \eqalign{ T_{\text{Average}}(n) &= c_6 \times (n-1) + (c_8 + c_9 + c_{18}) \times (n-1) + (c_{13} + c_{14} + c_{15}) \times \frac{(n-1)n}{4} \cr &= \frac{(c_{13} + c_{14} + c_{15})}{4} \times n^2 + (c_6 + c_8 + c_9 + c_{18} - \frac{(c_{13} + c_{14} + c_{15})}{4}) \times n \cr &\quad - (c_6 + c_8 + c_9 + c_{18}) \cr &= a \times n^2 + b \times n + c } $$其中， $a = \frac{(c_{13} + c_{14} + c_{15})}{4}$， $b = (c_6 + c_8 + c_9 + c_{18} - \frac{(c_{13} + c_{14} + c_{15})}{4})$。可以看出，此种情况下，插入排序算法的时间开销 ($T(n)$) 与输入列表的大小 $n$ 仍然成多项式关系，且最高次为二次。
从以上分析中可以看出，算法的执行效率通常与输入规模 $n$ 密切相关。随着输入规模的增加，算法的执行成本也会随之变化。比如说，当 len(arr) == 10 与 len(arr) == 10000 时，插入排序的执行成本差异将非常明显。对于规模较小的输入（如 $n=10$），插入排序的操作次数相对较少，即使在最差情况下，算法的运行时间仍可以在合理的范围内完成。然而，当输入规模扩展到 $n=10000$ 时，插入排序的性能将显著下降，特别是在最差情况下，算法的运行时间会急剧增加。这种增长主要源于插入排序的核心逻辑涉及的嵌套循环结构，其总执行次数随 $n$ 的平方增长。
而同一规模下，算法的执行成本也可能因为输入数据的状态而不同。例如，在插入排序中，当输入列表接近升序排列时，算法的效率最高，每次插入操作只需较少的比较或移动。而当输入列表完全无序时，算法的效率会降低，每次插入操作需要更多的比较或移动。如果输入列表是严格降序排列的，算法的效率最低，因为每次插入操作都需要最大次数的比较和移动。
在分析算法效率时，尽管最优情况、最差情况和平均情况都很重要，但通常我们更关注最差情况的分析。这是因为最差情况能够为我们提供算法在极端条件下的性能保证，帮助评估算法的可靠性和稳健性。在实际应用中，输入数据的排列状态可能是不可控的，无法保证处于某种理想状态（如接近升序）。因此，通过分析最差情况，我们可以了解算法在最坏条件下的表现，从而为系统设计提供有力的依据。
由此可见，算法效率不仅与输入规模有关，还受输入数据初始状态的影响。虽然算法在最优情况下可能表现出较高的效率，但最差情况的分析更具有实际意义，因为它能够帮助我们评估算法的极限性能和稳定性，为选择和优化算法提供重要的参考。
除此之外，我们还可以看出一个重要的特征，那就是常数项和低阶项对算法效率增长趋势（Order of growth）的影响相对较小。在算法的效率分析中，尽管常数项可能会影响算法的实际运行时间，但它们通常对算法的整体增长趋势并不起决定性作用。换句话说，随着输入规模 $n$ 的不断增大，常数项对总成本的影响会变得越来越微不足道。比如说，在插入排序的分析中，我们发现每一条基本语句的执行成本（如 $c_6 + c_8 + c_9 + c_{18} + c_{13}$ 等）都会对总成本产生一定的贡献，但这些成本是固定的，与输入规模 $n$ 无关。相比之下，涉及输入规模 $n$ 的项，特别是高阶项（如 $n^2$）会随着输入规模的增长迅速主导总成本。因此，当 $n$ 很小时，常数项可能在运行时间中占据较大的比例，但当 $n$ 足够大时，常数项的影响将被高阶项完全掩盖。
这一特性对算法设计和选择具有重要意义。在评估算法性能时，我们更关注输入规模的增长如何影响运行时间，而不是具体的常数因子和低阶项。这也是为什么在后续的渐进分析中，我们常常忽略常数项和低阶项，专注于描述算法运行时间的增长速率。这种抽象分析方法能帮助我们快速比较不同算法的效率，尤其是在处理大规模数据时，为选择最优算法提供理论依据。
在 insertion_sort() 函数的实现中，核心代码包含了插入排序算法的关键步骤，同时也加入了一些注释（Comments）。需要注意的是，这些注释的主要作用是帮助开发者交流和理解代码逻辑，而在实际执行函数时，计算机并不会执行这些注释。因此，从算法分析的角度来看，注释的执行代价 $c = 0$，即它们不会对算法的运行时间产生任何影响。因此，在评估算法的时间复杂度时，我们不考虑注释的执行成本。
增长趋势（Order of Growth）与渐进分析（Asymptotic Analysis）
当我们计划对某一个算法进行效率分析时，是不是每次都需要像上面分析插入排序那样，逐条语句地计算执行次数、推导总成本呢？虽然这种方法很严谨，但显然并不高效，尤其是当算法变得更复杂，或者输入规模 $n$ 变得更大时，这样的分析过程会让我们抓不住重点。
在算法分析中，我们关心的核心问题是：当输入规模 $n$ 增大时，算法的运行时间（或资源消耗）如何增长？ 这被称为算法的增长趋势（Order of Growth）。增长趋势并不是要精确计算每条指令的执行成本，而是关注输入规模 $n$ 增加时，算法运行时间的大致增长模式。正如前面提到的，在分析插入排序的过程中我们发现：常数项和低阶项对算法效率的影响在输入规模较小时可能显著，但当 $n$ 增大时，这些成本会逐渐被高阶项掩盖。所以说，对于大规模输入来说，决定算法效率的关键在于其增长速率。例如，在插入排序中：当输入是严格升序时，算法的运行时间与 $n$ 成线性关系（即，$ T(n) \varpropto n $）, 当输入是严格降序时，算法的运行时间与 $n^2$ 成正比(即，$ T(n) \varpropto n^2 $)。显然，输入规模 $n$ 增大时，算法运行时间的增长趋势决定了它能否在实际中有效运行。
为了更加系统地描述算法的增长趋势，我们使用渐进分析（Asymptotic Analysis）。它是一种忽略常数项和低阶项，只关注高阶项的分析方法。通过渐进分析，我们能够提炼出算法复杂度的本质，方便地比较不同算法的效率。在渐进分析中，常用的表示法包括：
- 大 $O$ 表示法（Big-O Notation）：用于描述算法在最坏情况下的增长速率。它表示一个上界，例如插入排序的最坏情况时间复杂度可以表示为 $O(n^2)$。
- 大 $\Omega$ 表示法（Big-Omega Notation）：用于描述算法在最优情况下的增长速率。插入排序的最优情况时间复杂度是 $\Omega(n)$。
- 大 $\Theta$表示法（Big-Theta Notation）：用于描述算法在平均情况下的增长速率，给出一个上下界的准确范围。
渐进分析的核心在于回答以下问题：当输入规模 $n$ 趋于无穷大时，一个算法的执行时间或资源消耗如何增长？设一个函数 $T(n)$ 描述算法的运行时间。渐进分析的目标是找到一个更简单的函数 $f(n)$，用来描述 $T(n)$ 在 $n \rightarrow \infty$ 时的主要增长特性，使得 $T(n)$ 和 $f(n)$ 的增长速率相同或非常接近。从几何的角度看，渐进分析关注的是 $T(n)$ 和 $f(n)$ 的曲线在 $n$ 趋向无穷时的“斜率”或“增长形状”。虽然 $T(n)$和 $f(n)$ 可能有细微的差别（如低阶项），但它们在高阶增长趋势上是相似的。
例如，对于 $T(n) = 5n^2 + 3n + 2$，当 $n \rightarrow \infty$时， $n^2$ 是主要影响增长速率的部分。低阶项 $3n+2$ 和常数因子 5 的影响变得可以忽略。因此，我们用 $f(n) = n^2$ 来表示 $T(n)$ 的主要增长特性。
理解了基本原理，我们就可以给出以上三种表示法的更为严格的数学定义。
- 大 $O$ 表示法（Big-O Notation）：表示 $T(n)$ 的上界。$T(n) \in O(f(n))$ 意味着 $T(n) \leq c \times f(n)$，当$n \geq n_0$ 时，存在常熟 $c, n_0 > 0$。
- 大 $\Omega$ 表示法（Big-Omega Notation）：表示 $T(n)$ 的下界。$T(n) \in \Omega(f(n))$ 意味着 $T(n) \geq c \times f(n)$，当$n \geq n_0$ 时，存在常熟 $c, n_0 > 0$。
- 大 $\Theta$表示法（Big-Theta Notation）：表示 $T(n)$ 的准确增长速率。$T(n) \in \Theta(f(n))$ 意味着 $c_1 \times f(n) \leq T(n) \leq c_2 \times f(n)$，当$n \geq n_0$ 时，存在常熟 $c_1, c_2 n_0 > 0$。 这表示 $T(n)$ 的增长既不会快于 $f(n)$，也不会慢于 $f(n)$。
在数学中，渐进分析（Asymptotic Analysis） 是研究函数在某个点附近（通常是无穷远点）行为的一种方法。它关注的是函数的增长速率或收敛行为，而不是函数的具体值。通过渐进分析，我们可以用简单的数学表达式描述复杂函数在极限情况下的主要特性，忽略不重要的部分（如常数和低阶项）。
渐进分析从数学上为算法分析提供了一个抽象的视角，忽略了具体实现中的细节和硬件环境的影响，而是专注于描述算法效率的增长趋势。这种方法让我们能够清晰地比较不同算法在大规模输入下的性能表现，为我们选择更高效的算法提供了理论依据。
几条重要的基本规则
不管是大 $O$ 还是大 $\Omega$ ，它们本质上都是描述算法效率增长趋势的一种数学表示方法，它们告诉我们一个算法在不同输入规模下的增长上界或下界，但并不直接教我们如何分析或计算算法的具体效率。为了结合这些渐进表示方法来准确确定某个算法的效率，我们需要基于算法的逻辑结构进行分析，并借助一些经典的分析技巧和规律，比如如何分析循环、递归调用的执行成本等。
Rule 1： 循环（Loops）的时间复杂度。对于一个简单的循环，如果循环的迭代次数是 $n$ ，且循环体中的每个操作的成本为常数，则整个循环的时间复杂度是迭代次数与单次操作成本的乘积。用公式可以表示为：如果循环体的时间成本为 $O(f(n))$，循环运行 $n$，则总时间复杂度为 $ O(n \times f(n))$。比如：
1for i in range(n): # 迭代 n 次
2 a += 1 # 每次执行常数操作
则，其时间复杂度为 $ O(n \times f(n)) = O(n \times 1) = O(n)$。
Rule 2：嵌套循环（Nested loops）的时间复杂度。对于嵌套循环，外层循环的每次迭代都会执行内层循环，而内层循环的总次数通常与外层循环的变量有关。如果外层循环运行 $n$ 次，内层循环每次运行 $m(i)$ 次，则总时间复杂度为：$ O(\sum_{i=1}^n m(i) \times f(n))$。比如：
1for i in range(n): # 外层循环运行 n 次
2 for j in range(i): # 内层循环运行 i 次
3 a += 1 # 每次执行常数操作
其时间复杂度为：$O(\sum_{i=1}^n m(i) \times f(n)) = O(\sum_{i=1}^n i \times 1) = O(\frac{n(n-1)}{2}) = O(n^2)$
Rule 3：连续语句（Consecutive statements）。如果一个程序片段由多条连续执行的语句组成，那么这些语句的总运行时间复杂度是这些语句复杂度的加法，但最终的总复杂度由最高复杂度的那部分决定。换句话说，多条连续语句的总时间复杂度取决于其中最大的复杂度项。例如，以下程序片段包含两部分操作：
1for i in range(n): // 单层循环, 复杂度 O(N)
2 a[i] = 0
3
4for i in range(n): // 双层循环, 复杂度 O(N^2)
5 for j in range(n):
6 a[i] += a[j] + i + j
第一部分为一个简单的单层循环，复杂度为 $O(n)$；第二部分为一个嵌套双层循环，复杂度为 $O(n^2)$。根据该规则，整个程序片段的总时间复杂度为 $O(n^2)$。总结来说就是连续语句的总时间复杂度等于所有语句复杂度中的最大值，最高的复杂度决定一切。
Rule 4：if/else。if/else 语句的运行时间复杂度等于条件判断语句的运行时间，加上分支语句 S1 和 S2 中运行时间较大的那一部分。换句话说，if/else 的总运行时间由条件判断时间和两个分支中最大运行时间共同决定。
1if condition:
2 S1
3else:
4 S2
比如说，条件判断语句(condition)的运行时间为常量时间 $O(1)$，分支语句 S1 的运行时间为 $O(n)$，而分支语句 S2 的运行时间为 $O(n^2)$。则整个 if/else 语句的运行时间复杂度为：$O(1) + \max(O(N), O(N^2)) = O(N^2)$。可以简单理解为最大分支的复杂度决定了整个语句的复杂度。
Rule 5：递归的时间复杂度。递归算法的复杂度可以借助于一个叫做主定理（Master Theorem）的递归关系式（Recurrence Relation）来求解。
主定理（Master Theorem）：对于递归关系
$$ T(n) = aT(\frac{n}{b}) + O(n^d) $$其中， $a$ 表示子问题的个数，即每次递归中问题被分解成的子问题数量；$b$ 表示子问题的规模缩小因子，即原问题的规模 $n$ 每次递归后缩小到 $\frac{n}{b}$；$d$ 表示非递归部分的复杂度指数，即分解和合并的开销，其时间复杂度为 $O(n^d)$。则，总的时间复杂度的渐进行为取决于 $a$，$b$，$d$ 之间的关系。如果
- $d < \log_b a$， 则 $T(n) = O(n^{\log_b a})$;
- $d = \log_b a$， 则 $T(n) = O(n^d \log_b n)$;
- $d > \log_b a$， 则 $T(n) = O(n^d)$。
比如说
1def merge_sort(arr):
2 """
3 归并排序的主函数
4 :param arr: 待排序的列表
5 :return: 排序后的列表
6 """
7 if len(arr) <= 1:
8 return arr # 递归终止条件
9
10 # 分解阶段：将数组分成左右两部分
11 mid = len(arr) // 2
12 left_half = merge_sort(arr[:mid]) # <-- 对左半部分递归排序
13 right_half = merge_sort(arr[mid:]) # <-- 对右半部分递归排序
14
15 # 合并阶段：将两个有序数组合并成一个有序数组
16 return merge(left_half, right_half) # <-- 合并算法的时间复杂度为 O(n)
可以发现 $a = 2$，$b = 2$，$d = 1$，那么 merge_sort() 的时间复杂度有递归关系 $T(n) = 2T(n/2) + O(n) = O(n\log n)$。
关于主定理更为详细的介绍，请参考 Cormen et al.(2022) 第四章第5、6小节。
练习
以下是一个多层嵌套的程序，请根据代码，应用规则 1 至规则 5 分析其时间复杂度，并给出完整的推导过程。
1def complex_algorithm(arr, n):
2 # 第一部分：简单循环
3 for i in range(n):
4 for j in range(3): # 固定次数循环
5 arr[i] += j
6
7 # 第二部分：嵌套循环
8 for i in range(n):
9 for j in range(i):
10 arr[i] += arr[j]
11
12 # 第三部分：if/else 条件语句
13 if n % 2 == 0:
14 for i in range(n):
15 for j in range(n):
16 arr[i] += arr[j]
17 else:
18 for i in range(n):
19 arr[i] += i
20
21 # 第四部分：递归调用
22 def recursive_part(x):
23 if x <= 1:
24 return 1
25 return recursive_part(x // 2) + recursive_part(x // 2) + x
26
27 result = recursive_part(n)
28 return result
参考答案：