斯坦福 算法1 第二周笔记

来自斯坦福网站的Algorithms: Design and Analysis，与目前coursera上的版本内容没有变化，不过时间安排略有不同。

1 The Master Method

这个方法是一个用来在数学上分析递归算法计算复杂度的常用方式。

1.1 介绍

比如第一周课程里讲到的关于两个整数乘法的递归算法。naive的算法是每次递归成4个更小的整数乘法，复杂度的递推式为 $T(n) \leq 4T(n/2) + O(n)$T(n)≤4T(n/2)+O(n)，而改进版本是每次递归成3个更小的整数乘法，递推式为 $T(n) \leq 3T(n/2) + O(n)$T(n)≤3T(n/2)+O(n)。the master method就是用来分析比较这种形式的算法复杂度。

这个方法是一个可以直接应用的公式，相当于一个黑箱。它的应用前提是每次递归分成的小的问题是同样大小的（整数除不尽的那种也可以）。其正式描述如下：

而对应这个问题描述，相应的算法复杂度结果如下：

1.2 举例

可以举几个例子来验证这个方法的正确性。

1. 归并排序: a=2,b=2,d=1对应第一种，结果是$O(nlogn)$O(nlogn)。
2. 二分查找: a=1,b=2,d=0对应第一种，结果是$O(logn)$O(logn)。
3. naive的递归整数乘法: a=4,b=2,d=1对应第三种，结果是$O(n^{2})$O(n2)。
4. 高斯改进的递归乘法: a=3,b=2,d=1对应第三种，结果是$O(n^{1.59})$O(n1.59)。
5. strassen矩阵乘法: a=7,b=2,d=2对应第三种，结果是$O(n^{2.81})$O(n2.81)。
6. 假设一个递归: a=2,b=2,d=2对应第二种，结果是$O(n^{2})$O(n2)。

1.3 证明

将当前的条件与假设写成如下形式：

可以考虑利用在归并排序中用过的递归树的形式来完成证明。用递归树的方式最重要的一条就是计算出每一层中有多少个subproblem，每个subproblem有多少数据。

在当前假设下，第j层中有$a^{j}$aj个subproblem，而每个subproblem有$n/b^{j}$n/bj个数据。递归树一共有$log_{b}n$logb​n层。于是在第j层中，所有的计算量的上限为：$a^{j}*c*(\dfrac{n}{b^{j}})^{d} = cn^{d}*(\dfrac{a}{b^{d}})^{j}$aj∗c∗(bjn​)d=cnd∗(bda​)j。最后将每一层的计算量加起来，得到整个算法的计算量为：$total work \leq cn^{d}*\sum_{0}^{log_{b}n}(\dfrac{a}{b^{d}})^{j}$totalwork≤cnd∗∑0logb​n​(bda​)j。

对于每一层来说，计算量的分别与a成正比而与$b^{d}$bd成反比。他们有各自的物理意义：

而且它们的比值正好对应了三种不同的结果。因此可以更细致地观察三种结果对应的物理意义：

1. $a = b^{d}$a=bd: total work $\leq cn^{d} x \sum_{j=0}^{log_{b}n}1 = cn^{d}(log_{b}n+1) = O(n^{d}logn)$≤cndx∑j=0logb​n​1=cnd(logb​n+1)=O(ndlogn) (case1中每一层的计算量相同）
2. $a &lt; b^{d}$a<bd: total work $\leq cn^{d} x \sum_{j=0}^{log_{b}n}r^{j} = O(n^{d})$≤cndx∑j=0logb​n​rj=O(nd)。其中$r = \dfrac{a}{b^{d}} &lt; 1$r=bda​<1，因此其等比数列求和为常数。（case2 的结果由第一层的计算量决定）
3. $a &lt; b^{d}$a<bd: total work $\leq cn^{d} x \sum_{j=0}^{log_{b}n}r^{j} = O(n^{d}r^{log_{b}n}) = O(a^{log_{b}n}) = O(n^{log_{b}a})$≤cndx∑j=0logb​n​rj=O(ndrlogb​n)=O(alogb​n)=O(nlogb​a)。其中$r = \dfrac{a}{b^{d}} &gt; 1$r=bda​>1。（case3 结果由最后一层的叶子节点数量决定）

于是The Master Method得到证明。

2 QuickSort-Algorithm

这里的排序问题是指输入一个无重复数字的无序数组，得到一个由输入的相同组成但是升序排列的数组。（有重复数字的作为练习）

快排的核心思想是partition：选取数组中的一个元素作为中继（pivot），然后将小于它和大于它的数分别放在这个中继的两边。partition的操作复杂度是O(n)的，而且能够减小排序问题的规模。

2.1 partition操作

基于partition的思想，得到QuickSort算法的思路：

partition的两个特点，无额外开销的线性复杂度以及减小问题规模。思路如下：将第一个数作为pivot，然后用两个下标i和j分别表示当前已排序的两个部分的尾部。i指向的是第一个不小于pivot的数，而j则指向第一个未遍历的数。若j指向的数比pivot小则交换i与j位置的数并各自加一，否则j独自加一。当j到达尾部，交换i-1位置的数与pivot的位置。

2.2 正确性证明

于是partition之后得到了由pivot分割成左右两个部分的数组，且左边都小于pivot，右边都大于pivot。于是我们可以用归纳法证明算法的正确性。首先回忆一下归纳法：

对于快排来说目标命题P(n)指的是，快排算法正确地将长度n的输入数组排序了。

1. 对于n=1的情况显然满足。

2. 那么就需要证明第二点递推情况：假设$k_{1},k_{2} &lt; n$k1​,k2​<n且分别是一个数组pivot两边分割后两个部分的长度。$P(k_{1}), P(k_{2})$P(k1​),P(k2​) 成立指的是这左右两个部分都正确排序。由partition操作之后的数组分布得知左边小于pivot，右边大于pivot。又知道左右两边各自有序，因此整个数组有序，即$P(n)$P(n)成立，算法正确性得证。

2.3 pivot选取

在进行partition操作时pivot的选取能够决定整个算法的运行时间。可以分别考虑两种情况：

1. 一个有序数组运行快排，每次选取第一个数作为pivot。整体的运行时间为$O(n^{2})$O(n2)。
2. 一个无序数组运行快排，每次选取当前数组的中位数作为pivot，整体运行时间为$O(nlogn)$O(nlogn)。

所以该如何选取pivot呢？一个最简单的方式就是随机选取。随机选取或许就已经足够好了，直观的看，如果选的pivot在数组的25%-75%之间，分割的subproblem就足够好（O(nlogn)，可以自己证明），而随机选择有一半的几率选在这个区间内。

实际上有个理论，那就是如果快排中的pivot使用随机选取，那么快排算法的平均运行时间是$O(nlogn)$O(nlogn)。

3 QuickSort-Analysis

3.1 A Decomposition Principle

可以使用概率求期望的方法求快排算法的平均运行时间。可以将对应的样本空间以及对应的变量写成如下形式：

从算法流程可以观察得到，算法的运行时间由不同数字之间比较的次数决定。因此需要证明的就是每次算法进行比较的次数C的期望是$O(nlogn)$O(nlogn)的。

由于快排每次分成的subproblem并不是相同大小的，因此不能使用The Master Method来分析。于是我们可以定义一个新的变量$z_{i}$zi​表示A中第i大的数。于是可以得到一个新的变量来表示$z_{i}$zi​,$z_{j}$zj​在一次算法过程中比较的次数：

观察partition的过程，我们可以发现，如果$z_{i},z_{j}$zi​,zj​在一次partition中都不是pivot，那么它们在以后的过程中都不会再进行比较；只有其中之一是pivot，它们之间才会进行比较，而且比较了一次之后再也不会第二次比较。于是$X_{i,j}(\sigma)$Xi,j​(σ)的取值只有0和1。

因此对于任意的$\sigma$σ, $C(\sigma)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{i,j}(\sigma)$C(σ)=∑i=1n−1​∑j=i+1n​Xi,j​(σ)。于是得到$E[C]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}E[X_{i,j}]$E[C]=∑i=1n−1​∑j=i+1n​E[Xi,j​]。又因为$E[X_{i,j}] = Pr[X_{ij}=1]$E[Xi,j​]=Pr[Xij​=1]，所以得到$E[C]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}Pr[z_{i},z_{j}比较过]$E[C]=∑i=1n−1​∑j=i+1n​Pr[zi​,zj​比较过]

这里有一个普遍的规则，那就是计算一个复杂的随机变量的期望，可以先把它写为更简单的变量的和，然后利用期望的线性组合求解：

3.2 The Key Insight

于是关键就在于$z_{i},z_{j}$zi​,zj​两个数进行比较的概率。这个概率为$2/(j-i+1)$2/(j−i+1)，下面进行证明。

因为只有这两个数被选为pivot它们才会进行比较一次，否则永远不会比较，因此它们进行比较的概率就是它们会被选择为pivot的概率。于是得证。

放缩可得$E[C] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\dfrac{2}{j-i+1} \leq 2n*\sum_{k=2}^{n}\dfrac{1}{k} \leq 2n*ln(n)$E[C]=∑i=1n−1​∑j=i+1n​j−i+12​≤2n∗∑k=2n​k1​≤2n∗ln(n)。即证得快排的平均比较次数为$O(nlogn)$O(nlogn)，也就是平均运行时间为$O(nlogn)$O(nlogn)。

上式后一个不等式证明如下：