主定理与均摊复杂度

· · 算法·理论

前置

如果你对时间复杂度和渐进符号有基本了解，可以直接跳过这一部分。时间复杂度是代表算法用时随数据规模而增长的趋势。而渐进符号有很多种，其中大写表示严格含等于，小写则不含等于。包含以下几种，可以简单理解一下，\Theta 为比较精确的时间复杂度，O 是时间复杂度的上界，即最大值，\Omega 是时间复杂度的下界，即最小值。看完了前置内容，我们来看看文章的重心。

主定理

内容

对于任意递推式 T(n) = aT(\frac{n}{b}) + f(n) 且 \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^{k+1}n) & f(n) = \Theta(n^{\log_b a}\log^kn),k\ge 0 \end{cases}

且对于第二种情况来说，需要满足 \forall c < 1 且对于所有足够大的 n，af(\frac{n}{b}) \le cf(n)。

解释

如果你熟悉多项式，那么类比一下。对于情况一来说，f(n) = O(n^{(\log_b a) - \epsilon})，就表示在多项式中 f(n) < n^{\log_b a}；同理第二种表示 f(n) > n^{\log_b a}。因此对于不取等的两种情况，我们永远取较大的那一个。

应用

快速排序

我们都知道快速排序的最优时间复杂度为 O(n \log n)，那么我们怎么用主定理分析出来呢？最优的快速排序的递推式可以表示为 T(n) = 2T(\frac{n}{2}) + n，因为每次几乎都是均分为两部分，分别再次递归，回来时还需要整体处理一遍。那么根据主定理，显然 \log_b a = \log_2 2 = 1，那么实际上是满足第三种情况的，因为此时 f(n) = n = n^1\log^0n=n^{\log_b a}\log^kn，那么最优时间复杂度为 \Theta(n^{\log_b a}\log^{k+1}n)=\Theta(n\log n)。

任意递推式

给出任意递推式 T(n) = 3T(\frac{n}{2}) + \Theta(n)，那么我们计算出 \log_b a = \log_2 3，那么显然满足第一种情况，那么答案为 \Theta(n^{\log_2 3})。

均摊复杂度

以下文字摘自 oi-wiki:

均摊分析（Amortized Analysis）是一种用于分析算法和动态数据结构性能的技术。它不仅仅关注单次操作的成本，还通过评估一系列操作的平均成本，为整体性能提供更加准确的评估。均摊分析不涉及概率，且只能确保最坏情况性能的每次操作耗费的平均时间，并不能确认系统的平均性能。在最坏情况下，均摊分析通过将高成本操作的开销分摊到低成本操作上，确保整体操作的平均成本保持在合理范围内。

均摊分析通常采用三种主要分析方法：聚合分析、记账分析和势能分析。这些方法各有侧重，分别适用于不同的场景，但它们的共同目标是通过均衡操作成本，优化数据结构在最坏情况下的整体性能表现。

聚合分析法

聚合分析法就是通过计算一系列操作的总成本，并将其平均到每次操作上，从而得出每次操作的均摊时间复杂度。那么我们看动态数组，它在空间不够的时候会自动扩容，它主要有以下两种操作，第一种是如果还有空间，那么直接加入，时间复杂度为 O(1)；第二种是如果没有空间了，那么我就要进行扩容，此时我要把旧数组里的元素全部复制到新数组里，时间复杂度为 O(m)，m 为目前数组的大小。

那么假设我们要插入 n 个元素，那么根据情况分类计算。如果还有空间，我就要插入 n 次，总共为 O(n)。如果没有空间，我就要进行扩容，根据动态数组的性质，扩容会发生在空间不够时，且大小都是二的幂次，那么每次操作复制的成本为以二为公比的等比数列求和，那么复杂度近似 O(n)。综上，总复杂度为 O(n)，那么均摊到 n 次操作里的每一次操作的复杂度就是 O(1)。

记账分析法

以下文字摘自 oi-wiki:

记账分析法（Accounting Method）通过为每次操作预先分配一个固定的均摊成本来确保所有操作的总成本不超过这些预分配的成本总和。记账法类似于一种费用前置支付的机制，其中较低成本的操作会存储部分费用，以支付未来高成本的操作。

还拿动态数组举例，假设我给它每一个位置开始每次预设的成本为 3，每次插入和扩充一个位置只需要 1，那么对于每一次剩的成本我就可以存下来供后面使用。

具体举例：假如我一直插入 [1,+\infty] 的元素 i 分别放在 i 位置上，且数组从 1 下标开始，以下是插入 4 个元素的例子，初始数组 a = [1,2,3,4]，目标数组 a = [1,2,3,4,5,6,7,8]，0 表示空位置。

手推一下或者可以严格证明发现动态数组的每次插入操作所存储的均摊成本足够支付未来的扩容操作，就相当于开店不管挣不挣钱，都不需要再次往里砸钱了。那么每次插入的均摊复杂度为 O(1)。

势能分析法

以下文字摘自 oi-wiki:

势能分析（Potential Method）通过定义一个势能函数（通常表示为 \Phi），度量数据结构的 潜在能量，即系统状态中的预留资源，这些资源可以用来支付未来的高成本操作。势能的变化用于平衡操作序列的总成本，从而确保整个算法的均摊成本在合理范围内。

内容

首先我们定义分析的数据结构，设 P_0 为空白初始状态，\forall i \in [1,n]，P_i 是由 P_{i-1} 转移来的，设 c_i 为第 i 次操作的实际成本。那么就来到了势能分析法的核心——势函数，定义势函数 \Phi(P_i) 表示数据结构 P_i 状态下的势能。

那么我们定义均摊成本为：

\hat{c_i} = c_i + \Phi(P_i) - \Phi(P_{i-1})

那么总均摊复杂度可以表示为：

\sum_{i=1}^n \hat{c_i} = \sum_{i=1}^n [c_i + \Phi(P_i) - \Phi(P_{i-1})]

我们可以把求和展开，发现有许多可以互相消掉的项，得到的最终结果为：

\sum_{i=1}^n \hat{c_i} = \sum_{i=1}^n c_i + \Phi(P_n) - \Phi(P_0)

那么如果我们在定义势函数时，满足 \Phi(P_0) = 0 且 \forall i \in [1,n]，\Phi(P_i) \ge \Phi(P_{0})，那么 \sum_{i=1}^n \hat{c_i} \ge \sum_{i=1}^n c_i，因此我们可以用总均摊复杂度算法时间上界。

解释

分类讨论一下 \Phi(P_i) 和 \Phi(P_{i-1}) 的关系。如果 \Phi(P_i) > \Phi(P_{i-1})，那么就是相当于每次都在消耗额外的代价转化为当前的势能。反之，如果 \Phi(P_i) < \Phi(P_{i-1})，那么就是相当于每次都在消耗之前储存的额外的势能。取等的情况不做过多说明。

那么如果保证 \Phi(P_0) = 0 且 \forall i \in [1,n]，\Phi(P_i) \ge \Phi(P_{0})，那么也就是说，我需要消耗势能的操作所消耗的势能，都在前面储存了，也就是不需要消耗额外的成本。综上，我们只需要将本来成本消耗较大的操作势能降低即可。

应用

一道经典例题。定义一个栈，设 \mid S_i \mid 为它在第 i 次操作后的元素数量，即栈的大小。栈具有三种操作：操作一，加入一个元素；操作二，弹出一个元素；操作三，弹出前 k 个元素，保证元素数量 \mid S_i \mid \ge k。

那么三种操作的实际成本分别为 1、1，那么显然弹出 k 个实际成本为 1\times k = k。我们定义势函数 \Phi(P_i) = \mid S_i \mid，显然满足定义势函数的条件，因为最开始时，栈空大小为 0，那么 \Phi(P_0) = 0，所以我们可以用总均摊代价代表总实际代价的上界。

那么三种操作分别分类讨论当前操作的类别：

综上，我们发现总均摊成本为 O(n)，其中 n 为操作数，那么每个操作的均摊复杂度为 O(1)。

练习

动态数组在空间不够的时候会自动扩容，它主要有以下两种操作，第一种是如果还有空间，那么直接加入，时间复杂度为 O(1)；第二种是如果没有空间了，那么我就要进行扩容，此时我要把旧数组里的元素全部复制到新数组里，时间复杂度为 O(m)，m 为目前数组的大小。扩容会发生在空间不够时，且大小都是二的幂次。使用势能分析法分析均摊复杂度。

那么我们想让本来成本消耗较大的操作势能降低，那么针对这道题，我们就需要把扩容复制的势能降低，那么也就是说我要设计一个势函数，满足剩余数量越多势能越小，那么势函数可以设为 \Phi(P_i) = 2 \times num_i - size_i，其中 num_i 表示储存的数字个数，size_i 表示数组大小，显然满足条件。

那么依然分类讨论操作类型：

综上，我们发现总均摊成本为 O(n)，其中 n 为操作数，那么每个操作的均摊复杂度为 O(1)。

拓展

对于上面的两个经典案例，你可以用其他的方法计算它的均摊复杂度吗？