《算法导论》学习第一部分：算法的基础知识

大家好，欢迎来到IT知识分享网。

前言

《算法导论》第一部分内容

一、算法在计算中的作用

1.1 算法

定义：算法就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。

数据结构：一种存储和组织数据的方式，旨在便于访问和修改。

1.2 算法作用

二、算法基础

2.1 插入排序

也叫直接插入排序：基本操作是将一个记录插入到已经排序好序的有序表中，从而得到一个新的、记录数增1的有序表。

伪代码如下：

INSERTION-SORT(A): for j=2 to A.length key = A[j] //Insert A[j] into the sorted sequence A[1..j-1]. i=j-1 while i>0 and A[i]>key A[i+1]=A[i] i = i - 1 A[i+1] = key 

C语言实现如下：

#define MAXSIZE 10000 /*用于要排序数组个数的最大值，可根据需要修改*/ typedef struct { 
      int r[MAXSIZE+1]; /*用于存储要排序数组，r[0]用作哨兵或临时变量*/ int length; /*用于记录顺序表的长度*/ }SqList; void InsertSort(SqList *L) /*对顺序表L作直接插入排序*/ { 
      int i,j; for(i=2;i<=L->length;i++) { 
      if(L->r[i]<L->r[i-1]) /*需将L->r[i]插入有序子表*/ { 
      L->r[0]=L->r[i] /*设置临时变量,后续给插入点赋值*/ for(j=i-1;L->r[j]>L->r[0];j--) L->r[j+1]=L->r[j]; /*记录后移*/ L->r[j+1]=L->r[0]; /*插入到正确位置*/ } } } 

2.2 分析算法

分析算法的时间复杂度，算法运行时间与输入规模的关系。

2.3 设计算法

2.3.1 分治法

归并排序算法完全遵循分治模式。直观上其操作如下：
分解：分解待排序的n个元素的序列成各具有n/2个元素的两个子序列。
解决：使用归并排序递归地排序两个子序列。
合并：合并两个已排序的子序列以产生已排序的答案。

 MERGE(A,p,q,r) n1=q-p+1 n2=r-q let L[1..n1+1] and R[1..n2+1] be new arrays for i=1 to n1 L[i]=A[p+i-1] for j=1 to n2 R[j]=A[q+j] L[n1+1]=∞ R[n2+1]=∞ i=1 j=1 for k=p to r if L[i]<=R[j] A[k]=L[i] i=i+1 else A[k]=R[j] j=j+1 

归并排序的伪代码如下

MERGE-SORT(A,p,r) if p<r q=⌊(p+r)/2⌋ MERGE-SORT(A,p,q) MERGE-SORT(A,q+1,r) MERGE(A,p,q,r) 

运行时间为Θ(nlgn)。

三、函数的增长

3.1 渐进记号

插入排序的运行时间刻画为函数 an²+bn+c，通常我们写成Θ（n²），除去了该函数的部分细节。

Ο，读音：big-oh；表示上界，小于等于。

Ω，读音：big omega、欧米伽；表示下界，大于等于。

Θ，读音：theta、西塔；既是上界也是下界，称为确界，等于。

ο，读音：small-oh；表示上界，小于。

ω，读音：small omega；表示下界，大于。

Ο是渐进上界，Ω是渐进下界。Θ需同时满足大Ο和Ω，故称为确界。Ο极其有用，因为它表示了最差性能。

3.2 标准记号与常用函数

单调性：单增、单减、严格增、严格减

向上取整与向下取整：⌈⌉、⌊⌋

模运算：对任意整数a和任意正整数n，a mod n 的值就是商a/n的余数。

多项式、指数、对数、阶乘、多重函数、多重对数函数、斐波那契数。

四、分治策略

关键三步骤：分解、解决、合并。
递归式与分治方法是紧密相关的，因为使用递归式可以很自然地刻画分治算法的运行时间。

4.1 最大子数组问题

最大子数组：最大的非空连续子数组。

使用分治策略求解最大子数组

如图a，最大子数组必然位于以下三种情况：
1.完全位于中点左侧
2.完全位于中点右侧
3.跨越中点
如图b，任何跨越中点的子数组都由两个子数组A[i…mid]和A[mid+1…j]组成。
过程 FIND-MAX-CROSSING-SUBARRAY 接收数组A和下标low、mid、high为输入，返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中，值的和。

FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) left-sum = -∞ sum=0 for i=mid downto low sum = sum+A[i] if sum > left-sum left-sum = sum max-left=i right-sum = -∞ sum = 0 for j=mid+1 to high sum=sum+A[j] if sum>right-sum right-sum=sum max-right=j return (max-left,max-right,left-sum + right-sum) 

FIND-MAXIMUM-SUBARRAY(A,low,high) if high==low return (low,high,A[low]) //base case: only one element else mid=⌊(low+high)/2⌋ (left-low,left-high,left-sum) = FIND-MAXIMUM-SUBARRAY(A,low,mid) (right-low,right-high,right-sum) = FIND-MAXIMUM-SUBARRAY(A,mid+1,high) (cross-low,cross-high,cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) if left-sum>=cross-sum and left-sum>=right-sum return (left-low,left-high,left-sum) else if right-sum>=left-sum and right-sum>=cross-sum return (right-low,right-high,right-sum) else return(cross-low,cross-high,cross-sum) 

4.2 矩阵乘法的Strassen算法

若A=(aij)和B=(bij)是nn的方阵，则对i,j=1,2,…,n，定义乘积C=AB中的元素Cij为：Cij=∑aikbkj (下标是k=1,上标是n)；
下面过程接收n
n矩阵A,B，并返回他们的乘积C。假设每个矩阵都有一个属性rows。

SQUARE-MATRIX-MULTIPLY(A,B) n = A.rows let C be a new n*n matrix for i = 1 to n for j = 1 to n cij = 0 for k=1 to n cij = cij+aik*bkj return C 

该过程花费时间Θ（n³）, 后续的Strassen算法的运行时间为Θ（n^2.81）。

一个简单的分治算法
假定n是2的幂，则A,B,C都可以分解为4个n/2Xn/2的子矩阵，则可得以下四个公式：
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B21
C22=A21B12+A22B22
每个公式对应两对n/2Xn/2矩阵的乘法及n/2Xn/2积的加法，可以设计一个直接的递归分治算法：

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A,B) n=A.rows let C be a new nXn matrix if n==1 c11=a11*b11 else partition A,B, and C as 4 n/2Xn/2 submatrix C11=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11,B11)+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12,B21) C12=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11,B12)+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12,B22) C21=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21,B11)+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22,B21) C22=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21,B12)+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22,B22) return C 

运行时间的递归式为：T（n）= Θ(1),(若n=1) ； 8T(n/2)+Θ(n²),若n>1。后续4.5节求解递归式可以得到这种解法T(n)=Θ（n³）,所以分治算法并不优于SQUARE-MATRIX-MULTIPLY 算法。

Strassen方法
Strassen算法的核心思想是令递归树不那么茂盛一点，即只递归七次而不是八次n/2Xn/2矩阵的乘法。
包含4个步骤：
1.分解矩阵为n/2Xn/2的子矩阵。采用下标计算方法，此步骤花费Θ（1）；
2.创建10个n/2Xn/2的矩阵S1,S2…,S10，每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间Θ（n²）。
3.用步骤1和2中的矩阵，递归地计算7个矩阵积P1,P2,…,P7。每个矩阵Pi都是n/2Xn/2。
4.通过Pi矩阵的不同组合进行加减运算，计算出C11,C12,C21,C22,花费时间Θ（n²）。
Strassen算法运行时间T（n）的递归式：T（n）= Θ(1) ,若n=1; 7T(n/2)+Θ（n²）, 若n>1。
利用4.5节的主方法可以求出T(n) = Θ(n^lg7)。

Strassen算法细节
（1）创建如下十个矩阵：
S₁=B₁₂ – B₂₂
S₂=A₁₁ + A₁₂
S₃=A₂₁ + A₂₂
S₄=B₂₁ – B₁₁
S₅=A₁₁ + A₂₂
S₆=B₁₁ + B₂₂
S₇=A₁₂ – A₂₂
S₈=B₂₁ + B₂₂
S₉=A₁₁ – A₂₁
S₁₀=B₁₁ + B₁₂
（2）创建七次矩阵乘法：
P₁=A₁₁*S₁
P₂=S₂*B₂₂
P₃=S₃*B₁₁
P₄=A₂₂*S₄
P₅=S₅*S₆
P₆=S₇*S₈
P₇=S₉*S₁₀
（3）计算出C矩阵：
C₁₁=P₅+P₄-P₂+P₆
C₁₂=P₁+P₂
C₂₁=P₃+P₄
C₂₂=P₅+P₁-P₃-P₇

4.3 用代入法求解递归式

4.4 用递归树方法求解递归式

在递归树中，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。

4.5 用主方法求解递归式

4.6 证明主定理

五、概率分析和随机算法

总结