斯坦福 算法1 第一周笔记

斯坦福 Algorithms: Design and Analysis 1 第一周笔记

• • INTRODUCTION

  • • 1.1整数乘法
    • 1.2 Merge Sort
    • 1.3 算法分析的三个准则

  • 2 ASYMPTOTIC ANALYSIS

  • • 2.1 大O表示法
    • 2.2 大\Omega表示法
    • 2.3 \Theta表示法

  • 3 DIVIDE & CONQUER ALGORITHMS

  • • 3.1 逆序对计数算法
    • 3.2 Strassen's 次立方矩阵乘法
    • 3.3 二维点最近距离的O(nlogn)解法

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

INTRODUCTION

1.1整数乘法

两个整数相乘的计算，即c=x y。假设x和y的位数是n，而以每个一位数的加法或乘法为基本操作，可得x y的计算中使用最原始的按位相乘然后相加的算法时需要的基本操作数量是n^{2}级别。举例如下，两个4位数相乘，每一行都要至少进行4次基本操作，共有4行：

但我们却可以做到更好。改良的算法叫做Karatsuba Multiplication，这是一个递归算法，计算x*y的结果流程如下：

• 令x=10^{n/2}a+b，y=10^{n/2}c+d
• x*y = (10^{n}ac+10^{n/2}(ad+bc)+bd)，于是只需要继续计算式子里的ac,ad,bc,bd四项的积即可。

针对每次递归需要计算的ac,ad,bc,bd还有个优化。分别计算需要做4次乘法，而实际上我们关心的是ac bc与(ad+bc)三项。可以通过计算ac bc与(a+b)(c+d)三次乘法得到结果。

1.2 Merge Sort

归并排序是一个简单的分治算法。上述的整数乘法的优化也是一种分治算法。

排序算法的输入是一个无序数组，输出是一个有序数组。而归并排序算法流程如下：

1. 递归地将当前数组的前一半与后一半分别排序
2. 将排序好的前一半与后一半合并为有序的整体

这里忽略了递归至最后只有一个数的时候的处理。其中第二步合并的伪代码如下：

所以如果合并后的数组长度为m，那么每个合并操作的基本操作数\leq 4m+2 \leq 6m。

将递归过程画成高为log_{2}n的一颗树：

第j行有2^{j}个排序问题，每个问题里数组长度为n/2^{j}。因此每一层中进行的操作数\leq 2^{j}*6(n/2^{j})=6n。于是整个归并排序算法的操作数上限为6n(log_{2}n+1)。

1.3 算法分析的三个准则

准则一：分析算法时一般根据最坏情况分析操作数的上限。这样做比较简单，不需要像平均分析那样需要知道样例的分布以及benchmarks方法需要提供样例。

准则二：不太在意结果的常数项以及低次项。因为更简单而且分析的粒度适中。

准则三：asymptotic analysis。也就是分析的输入样本数量n一般比较大。不关心较小时的情况。

因此在本门课里更快的算法就约等于最坏运行时间随着n增加而增长较慢的算法。

2 ASYMPTOTIC ANALYSIS

利用术语可以忽略掉常数项与低次项，例如大O表示法。

2.1 大O表示法

2.2 大\Omega表示法

2.3 \Theta表示法

有个重要的例子：

3 DIVIDE & CONQUER ALGORITHMS

3.1 逆序对计数算法

给定一个无序数组A，输出其逆序对的个数。逆序对是指在数组中的下标i < j，但是值A[i] < A[j]的一对数（A[i],A[j])。比如数组[1,3,5,2,4,6]中逆序对有(3,2),(5,2),(5,4)。

假如使用暴力方法，即两层遍历，其复杂度为O(n^{2})。假如想要做到更好，可以使用分治的思想，这是idea1。其中每一层的迭代计算的流程如下：

1. 左边：先计算i,j <= n/2时逆序对数量
2. 右边：计算n/2 < i,j时逆序对的数量
3. 跨边：计算i <= n/2 < j时逆序对的数量

伪代码如下：

    Count(array A, length n):
    if n = 1 return 0
    else
        x = count(A 的左半边, n/2)
        y = count(A 的右半边, n/2)
        z = countSplitInv(A,n)
        return x+y+z
    
    
      
      
      
      
      
      
      
    

因为目标复杂度是O(nlogn)，分治的递归调用深度是logn，因此每一层的实现只能是线性的。

idea2，可以使用基于merge sort的算法来实现两个数组合并时跨数组逆序对的计算也就是函数countSplitInv。因为merge sort算法能够自然地发现跨边的逆序对，只需要将其改为计数即可。

仔细观察归并排序中合并数组时的操作，我们发现当C中的2应该放入D中时B中依然留下3和5，这正代表了两个逆序对。而当4应当放入D中时B中还留下5，也表示了逆序对。即每次后一个数组C中的数应当放入D时，数组B剩余的数字都与C当前数组成逆序对，于是可以在线性时间内完成跨数组逆序对的计算，满足了要求。

3.2 Strassen’s 次立方矩阵乘法

矩阵乘法Z = X Y，矩阵维度为n n，其中
新数组中每个数的计算量都是\theta(n)，因此总体的计算复杂度是\theta(n^{3})。

假如使用如下分治方式：

每次需要计算8个递归的矩阵乘法以及相应的加法，计算复杂度依然是三次方（课程后面内容有证明）。

但是strassen使用了一些组合方式，让8次矩阵乘法减为7次，因此得到了比三次方更好的复杂度（后面课程证明）。

3.3 二维点最近距离的O(nlogn)解法

假如有一堆二维的点，需要计算出其中最近的两个点之间的距离（假设每个点的x与y都不相同），距离使用欧氏距离。暴力解法依然是两次循环，复杂度是O(n^{2})，而使用分治方法也能得到O(nlogn)的解法。

算法ClosestPair(P_{x},P_{y})思想如下：

• 先按x轴给点排序得到点集P_{x}，然后按y轴得到P_{y}。
• Q和R表示集合P的左右两边，那么Q_{x},R_{x}表示即由P_{x}分割两半而来的左右两部分。Q_{y},R_{y}同理（复杂度O(n))。即Q_{x},Q_{y}是P的左半边按x轴和按y轴排序的结果。
• (p_{1},q_{1}) = ClosestPair(Q_{x},Q_{y})
• (p_{2},q_{2}) = ClosestPair(R_{x},R_{y})
• \delta=两个点对距离的最小值
• (p_{3},q_{3}) = closestSplitPair(P_{x},P_{y},\delta)
• 返回三个点对中的最优值

算法的核心就在于计算左边和右边最短距离点对的函数 closestSplitPair(P_{x},P_{y},\delta)。此函数的流程如下：

其中S_{y}表示的是x值在区间[\widehat{x}-\delta,\widehat{x}+\delta]之间的P_{y}中的所有点。因为P_{y}按y值排序，因此也可以在线性时间得到按y值排序的点集。后面即是遍历S_{y}集合中的点，每个点与后面相连的7个点计算距离，留下最优的一对点。虽然有两个循环，但是第二个循环是常数复杂度，因此总复杂度是线性的。

看起来非常简单，但是如何能够证明这个算法的正确性呢？假设如下，如果证明假设正确，即可证明算法正确。

先证明假设A。A的证明其实很明显，如果存在更短距离的两个点，那么这两个点必然在集合S_{y}中。证明省略。

再证明假设B。假设B中的8究竟如何而来。假设B也可以分为两个引理分别证明。

引理1，可能存在的更近的点p和q必然落在如下8个小正方形里。正方形以p和q中较小的y值为底，往上\delta/2。以分割点的x值为中线，往左右各\delta，以\delta/2为单位划线。

证明：

引理2，每个小方格中最多只有1个点。证明也很简单，用反证法：

最终证明了算法的正确性。