分治

乘法的优化

暴力的乘法复杂度是\(O(n^2)\)的。

如果两个\(n\)位数\(x,y\)相乘（我们保证\(n\)是2的幂），那么我们按位把\(x\)分成\(x_L,x_R\)两半，\(y\)分成\(y_L,y_R\)，使得\(x=x_L \cdot 2^{n/2}+x_R,y=y_L \cdot 2^{n/2}+y_R\)。那么\(xy=x_Ly_L \cdot 2^n + (x_Ly_R+x_Ry_L)\cdot 2^{n/2}+x_Ry_R\)。加法和乘以2的幂次都是\(O(n)\)的，而余下的乘法可以递归的完成。设两个\(n\)位数的乘法所需时间是\(T(n)\)。那么有递推关系\(T(n)=4T(n/2)+O(n)\)。可以画出递归树解得\(T(n)=O(n^2)\)。

利用Guass's Trick，我们可以进行优化。我们可以计算出\(x_ly_L,x_Ry_R\)，再计算出\((x_L+x_R)(y_L+y_R)\)，用第三个数减去前两个数就可以得到交叉项。这样四次乘法就被优化到了三次。此时\(T(n)=3T(n/2)+O(n)\)。这时解变成了\(T(n)=O(n \cdot \left(\dfrac{3}{2}\right)^{\log n})=T(3^{\log_2 n})=T(n^{\log_2 3})\approx T(n^{1.59})\)

主定理

从上述例子中可以发现，分治算法的复杂度分析一般式为：

\(T(n)=aT(n/b)+O(n^d)\)

其中假设\(n\)是\(b\)的幂。

我们依然画出递归树。得到（\(k=\log_b n\)）

\(T(n)=O\left(n^d+a \cdot \dfrac{n^d}{b^d}+a^2 \cdot \dfrac{n^d}{(b^2)^d}+\cdots+a^k \cdot \dfrac{n^d}{(b^k)^d}\right)\)

这是等比数列，公比为\(\dfrac{a}{b^d}\)。因此需要分类讨论。

当\(a>b^d\)时，\(T(n)=O(n^d \cdot \dfrac{\frac{a^k}{b^{dk}}-1}{\frac{a}{b^d}-1})=O(a^{\log_b n})=O(n^{\log_b a})\)

当\(a=b^d\)时，\(T(n)=O(n^d \cdot k)=O(n^d \cdot \log_b n)=O(n^d \log n)\)

当\(a<b^d\)时，\(T(n)=O(n^d \cdot \dfrac{1-\frac{a^k}{b^{dk}}}{1-\frac{a}{b^d}})=O(n^d)\)

排序

归并排序满足\(T(n)=2T(n/2)+O(n)\)，解得\(T(n)=O(n \log n)\)。我们可以证明基于比较的排序算法不可能比这更优。

考虑给一个全排列\(\sigma\)排序，第一次比较\(\sigma_{i_1},\sigma_{j_1}\)两个元素。\(\sigma\)分为两类，一类满足\(\sigma_{i_1}<\sigma_{j_1}\)，一类满足\(\sigma_{i_1}>\sigma_{j_1}\)；在每一类中，又可以分为\(\sigma_{i_2}<\sigma_{j_2}\)和\(\sigma_{i_2}>\sigma_{j_2}\)。如果把这种分类看成一颗二叉树的话，它的叶节点就有\(n!\)个。排序算法的优劣就在于怎么选择每一次的\(i_k,j_k\)，因为这决定了二叉树的形态。为了让排序算法最优秀，一定要让最坏的也就是深度最大的叶节点的深度尽量小。因此这应当尽量是一颗平衡树（满二叉树），此时最大深度为\(\log_2 (n!)\)。根据Stirling's Formula，\(n! \sim \sqrt{2n\pi}\left(\dfrac{n}{e}\right)^n\)，因此\(O(\log n!)=O(n \log n)\)。可见任何排序算法的比较次数都不可能小于\(O(n \log n)\)这个量级。

Medians

求中位数的复杂度是可以优于排序的复杂度的。我们每次随机选择一个数\(v\)，把小于\(v\)的和大于\(v\)的挑出来，转化成在新的数组里找第\(k\)小的问题。我们不停随机这个\(k\)，直到挑到\(v\)的排名在\(1/4\)到\(3/4\)之间。由于概率为\(1/2\)，随机次数的期望是\(1/2+1/4+\cdots=2\)。因此可以写出期望复杂度\(T(n)=T(3/4n)+O(n)\)，解得\(T(n)=O(n)\)。

在理论计算机导论中，还学过一个并不随机的算法Median of Medians，复杂度是\(T(n)=T(\dfrac{n}{5})+T(\dfrac{7n}{10})+O(n)\)，解得\(T(n)=O(n)\)。