《Mathematical Analysis of Algorithms》是著名计算机科学家 Donald Knuth 在 1971 年发表的一篇论文，这篇论文的核心是对两个问题的算法分析，其中的运用的技巧是最值得我们关注的内容。
引言
算法分析可以分成两大类：
一、分析一个算法：对一个确定的算法，分析其时间复杂度、空间复杂度，在最坏情况下或平均情况下。
二、分析一类算法：对一个确定的问题，考虑所有解决这个问题的算法，找出哪一个最好，或者找出所有这类算法的复杂度下界。
第一类分析的历史较久，对第二类分析的研究起步稍晚。显然，第二类分析更加强大，因为可以同时分析无穷多个算法，然而，我们往往很难同时分析一个问题的所有算法，不得不把可能的算法限定在一定范围内。我们必须确定哪些操作是允许的，一旦定义有变，最优算法就会变化。比如基于比较的排序算法的复杂度下界是 \(O(n\log n)\)，但基数排序可以更优。
第二类分析没有取代第一类分析的主要原因有两个。一方面，为了进行分析我们必须建立一个简单的复杂度模型与算法模型，但这样的简单定义得到的最优算法往往不实用。另一方面，即便在简单的模型下，第二类分析仍然很困难。
因此，第一类分析在实用的角度上更重要，它可以考虑到一个算法的所有因素对复杂度的影响。并且，研究第一类分析的过程也能够给计算机科学提供更多的经验、技术与工具。
接下来，将对两个算法进行分析，它们不是最重要的算法，但也不是完全没用，分析的过程也包含着一些重要的想法。
内部置换(In Situ Permutation)
题目描述
给定一个数组 \((x_1,x_2,\cdots,x_n)\) 与一个 \(\{1,2,\cdots,n\}\) 的只读的排列 \(p\)，使用 \(O(1)\) 的额外空间将数组内容替换为 \(\left(x_{p(1)},x_{p(2)},\cdots,x_{p(n)}\right)\)，即只允许利用若干个辅助变量，在数组 \(x\) 内部按照排列 \(p\) 进行置换。
算法描述
首先，介绍一个关于排列与置换很常用的模型。如果有 \(n\) 个点，每个点 \(k\) 有一条连向点 \(p(k)\) 的有向边，那么这个图中每个点的出度和入度都为 \(1\)，因此这个图是由若干个环组成的。我们称一个环中编号最小的那个节点为环头，即满足 \(k<p(k),k<p(p(k)),k<p(p(p(k))),\cdots\) 的点 \(k\)。算法的主要步骤就是对于每一个点，判断它是不是环头，如果是环头的话，则沿着这个环进行置换，即临时记录下 \(x_k\)，令 \(x_k=x_{p(k)},x_{p(k)}=x_{p(p(x))},\cdots\)，直到绕环一圈回到环头。算法的伪代码如下，其中每一行被执行的次数被标在右侧：
复杂度分析
为了确定该算法的时间复杂度，需要对 \(a,b,c\) 进行分析。其中 \(a\) 代表判断环头所费的总时间，\(b\) 代表环的个数。由于数组 \(x\) 的每一项只会被赋值一次，结合伪代码第 10、11 行，可知 \(b+c=n\)，因此决定算法复杂度的因素只剩下 \(a\) 了。考虑最坏情况，若排列 \(p=(2,3,\cdots,n,1)\)，则只有一个环，对于每个点都必须不断向后查找直到回到点 \(1\) 才能判断出是不是环头，因此 \(a=(n-1)+(n-2)+\cdots+1=\frac{1}{2}(n^2-n)\)。在后面我们会看到，如果提供排列 \(p\) 的反函数 \(p^{-1}\)，则可以对算法作出一些小修改使得最坏复杂度达到 \(O(n\log n)\)。虽然这个算法在最坏情况下的复杂度达到 \(O(n^2)\)，平均情况下的复杂度仍非常重要。接下来我们将对 \(a,b\) 的均值和方差进行分析。（为什么要分析 \(b\) ？）
在分析之前，先介绍一种考虑排列上的环时常用的变换，它是一个排列到排列的双射。对于一个排列中的每个环，我们从环头开始依次写下它的元素，并用括号括起来，然后我们按照环头从大到小排序。例如，对于排列 \(p=(8,2,7,1,6,9,3,4,5)\)，它的环有 \((184)(2)(37)(569)\)，排序后为 \((569)(37)(2)(184)\)。最后，我们发现可以把括号去掉，因为环头一定是其前缀中最小的元素，得到 \(569372184\)。由此，我们得到了一个新的排列，它与原排列是一一对应的。下面我们假设排列 \((p(1),p(2),\cdots,p(n))\) 被这个变换变成了 \((q(1),q(2),\cdots,q(n))\)。
对 \(b\) 的分析
\(b\) 的值，即环的个数，即环头个数，即满足 \(\displaystyle q(j)=\min_{1\leqslant i\leqslant j}q(i)\) 的 \(j\) 的个数。环头个数为 \(k\) 的排列个数为第一类斯特林数 \(\displaystyle{n \brack k}\)（这就是第二类斯特林数的定义）。接下来证明 \(b\) 的期望值是调和级数 \(H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}\)。我们设 \[ x_j=\left\{\begin{array}{ll} 1,&\text{ if } q(i)>q(j) \text{ for } 1\leqslant i<j \text{ ; }\\ 0,&\text{ otherwise. }\\ \end{array}\right. \] 则 \(\displaystyle b=\sum_{j=1}^n x_j\)，则 \(\displaystyle E(b)=\sum_{j=1}^n E(x_j)\)，而 \(\displaystyle E(x_j)=\frac{1}{j}\)，因此 \(E(b)=H_n\)。
接下来证明 \(b\) 的方差为 \(H_n-H_n^{(2)}\)，其中 \(H_n^{(2)}=1+\frac{1}{4}+\cdots+\frac{1}{n^2}\)。\(Var(b)=E(b-E(b))^2=E(b^2)-E^2(b)\)，因此只要求出 \(\displaystyle E(b^2)=E\left(\sum_{j=1}^n x_j^2+2\sum_{1\leqslant i<j\leqslant n}x_i x_j\right)=\sum_{j=1}^nE(x_j^2)+2\sum_{1\leqslant i<j\leqslant n}E(x_ix_j)\)，其中 \(x_j^2=x_j\)，又有 \(\displaystyle E(x_ix_j)=\frac{1}{ij}\)，因此 \(\displaystyle E(b^2)=H_n+2\sum_{1\leqslant i<j\leqslant n}\frac{1}{ij}\)，而 \(E^2(b)=H_n^2\)\(=H_n^{(2)}+2\sum_{1\leqslant i<j\leqslant n}\frac{1}{ij}\)，因此 \(Var(b)=H_n-H_n^{(2)}\)。
对 \(a\) 的分析
\(a\) 的值的分析更加困难，但它也是决定算法复杂度的核心。对于点 \(i\)，我们依次查看 \(q(i+1),q(i+1),\cdots\) 是否大于 \(q(i)\)，直到找到最小的 \(r\) 使得 \(q(i+r)<q(i)\)，则点 \(i\) 对 \(a\) 的贡献为 \(r-1\)。类似的我们对 \(1\leqslant i<j\leqslant n\) 定义 \[ y_{ij}=\left\{\begin{array}{ll} 1,&\text{ if } q(k)>q(i) \text{ for } i<k\leqslant j \text{ ; }\\ 0,&\text{ otherwise. }\\ \end{array}\right. \] 则 \(\displaystyle a=\sum_{1\leqslant i<j\leqslant n}y_{ij}\)，则 \(\displaystyle E(a)=\sum_{1\leqslant i<j\leqslant n}E(y_{ij})\)，而 \(E(y_{ij})=\frac{1}{j-i+1}\)，因此 \(\displaystyle E(a)=\sum_{1\leqslant i<j\leqslant n}\frac{1}{j-i+1}=\sum_{r=2}^n\frac{n-r+1}{r}=(n+1)(H_n-1)-(n-1)=(n+1)H_n-2n\)。
\(Var(a)\) 计算类似，但过程太复杂此处略过，最终结果为 \(Var(a)=2n^2-(n+1)^2H_n^{(2)}-(n+1)H_n+4n\)。
优化的效果
根据以上分析，算法的平均时间复杂度为 \(O(n\log n)\)，虽然最坏情况下为 \(O(n^2)\)，但由于方差不大，最坏情况出现的概率不大。
我们对 \(a\) 和 \(b\) 的分析不仅能帮我们得到算法的复杂度，还可以用来考察算法优化的效果。考虑这样一个优化，我们有一个计数器 tally 初始值为 \(n\)，每当我们对数组 \(x\) 赋值，就将 tally 减一，因为 \(x\) 会被赋值 \(n\) 次，当 tally 为 \(0\) 时我们可以提前结束算法。添加这个优化我们需要执行 \(n\) 次 tally-- 与\(b\approx \log n\) 次 if(tally==0) ，而我们省略了多少操作呢？执行完最后一个环的环头后算法即可结束，最后一个环的环头是最大的环头，即 \(q(1)\)，所有大于 \(q(1)\) 的数都不会被主循环执行，因此第 \(4\) 行和第 \(7\) 行的执行次数由 \(n\) 减为 \(q(1)\)，平均减少次数为 \(0+1+\cdots+n-1=\frac{n(n-1)}{2}\)。第 \(6\) 行的执行次数，即 \(a\) 的值，减少的量为 \(\displaystyle\sum_{q(i)>q(1)}\sum_{j=i+1}^{n}y_{ij}\)，其平均值为 \(\displaystyle \sum_{2\leqslant i<j\leqslant n}\frac{1}{(j-i)(j-i+1)}=\sum_{r=2}^n \frac{n-r}{r(r-1)}=n-1-H_{n-1}\)。因此，此优化对复杂度的改进不大。
额外条件下的算法改进
假如我们得到了排列 \(p\) 的反函数 \(p^{-1}\)，我们可以对算法做一个改进。判断点 \(k\) 是不是环头时依次检查 \(p(k),p^{-1}(k),p(p(k)),p^{-1}(p^{-1}(k)),\cdots\)，即同时向前后两个方向检查。惊人的是，通过这样的改进能使算法的最坏时间复杂度达到 \(O(n\log n)\)。
我们设 \(f(n)\) 代表在一个长度为 \(n\) 的环中判断出所有非环头元素所花的总步数，其中同时探查 \(p^k(j)\) 与 \(p^{-k}(j)\) 被视为一步。则 \(f(1)=0\)，\(\displaystyle f(n)=\max_{1\leqslant k<n}\{\min(k,n-k)+f(k)+f(n-k)\}\)。假设环中最小元素（环头）到第二小元素的距离为 \(k\)，则判断第二小元素需要 \(min(k,n-k)\) 步，对于最小元素到第二小元素之间的 \(k-1\) 个数，以及第二小元素到最小元素之间的 \(n-k-1\) 个数，考虑判断它们所需的步数。对这两部分，我们可以分别将最小元素与第二小元素合并，连成一个长度为 \(k\) 与 \(n-k\) 的环，判断的步数分别为 \(f(k)\) 与 \(f(n-k)\)，因此总步数为 \(min(k,n-k)+f(k)+f(n-k)\)，得到了 \(f(n)\) 的递推公式。
这个递推式的解非常有趣，\(\displaystyle f(n)=\sum_{i=0}^{n-1}v(i)\)，其中 \(v(i)\) 表示 \(i\) 的二进制表示中 \(1\) 的个数。不知道这个解是怎么想出来的，其正确性可以用数学归纳法证明，但也十分复杂，论文也没有详细描述，此处略去。
由 \(f(2^k)=\) 所有 \(k\) 位二进制数中 \(1\) 的个数 \(=k2^{k-1}\)，可得 \(f(n)=O(n\log n)\).
选第 \(t\) 大(Selecting the \(t\)th Largest)
题目描述
给定数组 \(x[1..n]\) 与正整数 \(t\)，求数组中的第 \(t\) 大的数。
算法描述
在算法设计与分析课程内容中我们已经学习了一种最坏情况下 \(O(n)\) 时间复杂度的算法，这里我们考虑该算法的一个简化版。随机选择一个数，将其他数按照比它大或比它小分成两部分，其中 \(x[1..k-1]\) 的数比它大，\(x[k+1..n]\) 的数比它小，然后按照第 \(t\) 大的数在的范围递归查找。具体来说，若 \(k=t\)，则算法结束；若 \(t<k\)，则在 \(x[1..k-1]\) 中找第 \(t\) 大；若 \(t>k\)，则在 \(x[k+1..n]\) 找第 \(t-k\) 大。
复杂度分析
由于随机选取的数可能划分不均，最坏情况的复杂度可能达到 \(O(n^2)\)，但这种情况的概率是很小的。为了计算平均复杂度，设 \(C_{n,t}\) 表示在 \(n\) 个数里选第 \(t\) 大的数时的平均比较次数。则当 \(n>1\) 时有 \[ \begin{aligned} C_{n,t}=n-1+\frac{1}{n}(A_{n,t}+B_{n,t}) \end{aligned} \] 其中 \[ \begin{aligned} A_{n,t}&=C_{n-1,t-1}+C_{n-2,t-2}+\cdots+C_{n-t+1,1},\\ B_{n,t}&=C_{t,t}+C_{t+1,t}+\cdots+C_{n-1,t}. \end{aligned} \]
可以观察得到 \(A_{n+1,t+1}=A_{n,t}+C_{n,t}\) 与 \(B_{n+1,t}=B_{n,t}+C_{n,t}\).
因此可以利用差消法得到 \[ \begin{aligned} &(n+1)C_{n+1,t+1}-nC_{n,t+1}-nC_{n,t}+(n-1)C_{n-1,t}\\ =&(n+1)n-n(n-1)-n(n-1)+(n-1)(n-2)\\ &+A_{n+1,t+1}-A_{n,t+1}-A_{n,t}+A_{n-1,t}\\ &+B_{n+1,t+1}-B_{n,t+1}-B_{n,t}+B_{n-1,t}\\ =&2+C_{n,t}-C_{n-1,t}+C_{n,t+1}-C_{n-1,t}. \end{aligned} \] 因此 \[ \begin{aligned} C_{n+1,t+1}-C_{n,t+1}-C_{n,t}+C_{n-1,t}&=\frac{2}{n+1}\\ (C_{n+1,t+1}-C_{n,t})-(C_{n,t+1}-C_{n-1,t})&=\frac{2}{n+1}\\ \end{aligned} \]
方便起见，我们令边界值 \(C_{n,1}=C_{n,n}=n-1\)，迭代可得（注意此处与论文不同） \[ \begin{aligned} C_{n+1,t+1}-C_{n,t}&=\sum_{k=t+1}^{n}\frac{2}{k+1}+C_{t+1,t+1}-C_{t,t}\\ &=2(H_{n+1}-H_{t+1})+1 \end{aligned} \] 再次迭代可得 \[ C_{n,t}=\sum_{k=2}^{t}(2H_{n-t+k}-2H_{k}+1)+C_{n-t+1,1} \] 为了计算此式我们需要计算 \[ \begin{aligned} \sum_{k=0}^{n}H_k=&H_{n}-\frac{1}{n}-\frac{1}{n-1}-\cdots-\frac{1}{1}\\ +&H_{n}-\frac{1}{n}-\frac{1}{n-1}-\cdots-\frac{1}{2}\\ \vdots&\\ +&H_n-\frac{1}{n}\\ +&H_n\\ =&(n+1)H_n-n\cdot\frac{1}{n}-(n-1)\frac{1}{n-1}-\cdots-1\cdot\frac{1}{1}\\ =&(n+1)H_n-n \end{aligned} \] 因此可以得到 \[ \begin{aligned} C_{n,t}&=2(n+1)H_n-2(t+1)H_t-2(n-t+2)H_{n-t+1}+n+3\\ &=2(t+1)(H_n-H_t)+2(n-t)(H_n-H_{n-t+1})-4H_{n-t+1}+n-3\\ &\leqslant2(t+1)\frac{n-t}{t+1}+2(n-t)\frac{t-1}{n-t}-4H_{n-t+1}+n-3\\ &=3n-1-4H_{n-t+1} \end{aligned} \] 因此算法的平均时间复杂度是 \(O(n)\).
总结
以上的两个问题的分析是为了展示什么是算法分析，但由于问题过于复杂可能会模糊了 Knuth 想要表达的重点，最后他总结了他认为最重要的几点：
- 算法分析对计算机科学很重要
- 算法分析与离散数学密切相关
- 算法分析正在形成科学方法
- 算法分析领域还有很多问题没有解决