算法导论第二章——算法基础

1. 插入排序

我们的第一个算法，求解排序问题。

输入：

n个数的一个序列< $a1,a2,...,an$ >

输出:

输入序列的一个排列 < $a1',a2',...,an'$ >,满足 $a1'<=a2',...,<=an'$

我们也将希望排序的数称为关键词

我们首先介绍插入排序，对于少量元素这是一个有效的算法。工作方式类似于扑克牌的排序，从桌子上拿走一张牌，并插入手牌中正确的位置，使得手牌总是排序好的。从桌子上拿的牌也是牌堆中的第一张牌。

python算法描述

def insertionSort(A):
    n = len(A)
    for j in range(1,n):
        key = A[j]
        i = j-1
        while i>=0 and A[i]>key:
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key

循环不变式与算法的正确性

该图表面对 $A=<5,2,4,6,1,3>$ 该算法的工作流程。下标j指出准备要插入手中的当前牌，而 $A[1..j-1]$ 的子数组构成了已排好序的牌，剩余的数组对应于仍在桌子上的牌堆。我们把 $A[1..j-1]$ 所具有的性质称为循环不变式。即每次循环都有这种性质。

运行图解

循环不变式主要用于帮助我们理解算法的正确性。
关于循环不变式，我们必须证明三条性质：

初始化：循环的第一次迭代之前，它为真
保持：如果循环的某次迭代之前它为真，那么下次迭代之前仍为真
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

一二两条类似于数学归纳法，即相当于基本情况和归纳步，若证明成功，即循环的每次迭代前循环不变式都为真。

第三条意味着我们将用循环不变式来证明正确性，通常，我们和导致循环终止的条件一起使用循环不变式。

下面我们来看看，对于插入排序证明这些性质成立。

初始化

在第一循环( $j=2$ )之前，循环不变式成立，因为子数组仅有单个元素构成。

保持

我们给个非形式化的证明：
for循环中将 $A[j-1],A[j-2]..A[j-n]$ 等向右移动一个位置，直到 $A[j]$ 找到适当的位置。而后将 $A[j]$ 插入该位置，这时子元素仍由原来 $A[1..j]$ 的元素构成，但已有序。以此，每次对j增加构成的新子数组均有序。

终止

导致for循环终止的条件是 $j>A.length=n$ ,因此将j不断加一时，必有j=n+1,在循环不变式表述中将j用n+1代替，那么子数组由 $A[1..n]$ 的元素组成，但已排序，因此算法正确。

2.分析算法

分析算法的意味着预测算法需要的资源，我们最想度量的是时间。
为了分析算法，我们需要有一个实现技术的模型，包括描述所有资源及其代价的模型。我们使用一中假定的通用单处理器计算模型——随机访问机(RAM)。在RAM中，指令一条接一条执行，没有并发操作。

我们要注意不能滥用RAM模型，RAM模型只能完成基本操作，基本观点是，计算机如何设计，RAM就如何设计。

RAM中的数据类型有整型和浮点型，我们大部分情况下不关注精度，除非某些特殊应用。

在真实的计算机中还包含一些特殊指令，我们尽量避免这些指令。例如计算 $2^k$ ，当k较小时，我们当作常量时间计算。

我们在RAM模型中并不试图对内存层次进行建模。有些情况下会考虑内存层次的影响，但是大部分情况下不会。

插入排序算法的分析

插入排序算法需要的时间依赖于输入和被排序的程度。一般来说，算法的时间与输入的规模同步增长，所以通常把一个程序的运行时间描述成其输入规模的函数。

输入规模的概念依赖于研究的问题，如排序问题中，是输入的项数n，整数相乘时，是整数的位数。对于图，则使用顶点数和边数来描述。

一个算法在特定输入上的运行时间是指执行指令的操作次数。我们可以假定 $第i行代码执行的时间为ci$

如图所示，我们首先看看插入排序每条语句执行的次数和时间。注：while/for 等循环退出时会多执行一次

插入排序.jpg

该算法的运行时间是每条语句的运行时间之和

我们对运行时间求和，得到

运行时间求和.jpg

当是最好情况下，即数组已经排好序时，可以观察到第6行，第七行不会被执行，因此求和公式可更改为

最好情况求和.jpg

我们可以把该运行时间表示为

an+b

，因此T(n)是n的线性函数。

当输入已经反向排序时，将导致最坏情况。我们必须将 $A[j]$ 和 $A[1..j-1]$ 中的每个元素相比较，因此得到求和公式

最坏情况.jpg

即T(n)为n的二次函数。

最坏情况与平均情况分析

在本书的其他部分，我们往往集中于最坏情况运行时间分析，原因有三

最坏情况运行时间给出了上界，知道了这个上界就能确保算法绝不需要更长的时间。
对某些算法，最坏情况经常出现。
平均情况往往和最坏情况大致一样差

在某些特定情况下，我们会对算法的平均情况感兴趣，我们将看到概率分析技术被用于各种算法。平均情况分析范围有限，对于特定的问题，难以辨别什么才是平均情况。我们假设各种输入具有相同的可能性，实际上该假设可能并不成立。

增长量级

我们真正感兴趣的是运行时间的增长率或增长量级，所以我们只考虑公式中最重要的项。

3. 设计算法

我们可以选择使用的算法设计技术有很多，插入排序使用了增量方法，本节我们将讨论分治法，分治法的优点之一是，通过一些特殊技术往往很容易确定其运行时间。

1. 分治

分治法思想：将原问题分解为几个规模较小但类似原问题的子问题，递归地求解子问题，再合并这些子问题的解来得到原问题的解。

分治模式在每层递归时通常都有三个步骤

分解原问题为若干子问题，子问题为原问题的规模较小的实例
解决这些子问题，递归求解各子问题
合并这些子问题得到原问题的解。

归并排序算法完全遵循该模式，将n个元素分解为n/2个元素，使用归并排序递归解决子数列，合并已排序的子数列得到答案。

归并排序的关键步骤是合并已排序好的子数列，如两个已排序好的数列 $A[p..q]和A[q+1..r]$ ，合并完成这两个子数组得到新数组 $A[p..r]$

合并操作需要 $Θ(n)$ 的时间，我们不断比较两个子数组，选取较小的元素放入新数组
中完成合并。

使用python代码描述合并过程：

inf = float("inf")
def merge(A,p,q,r):
    L = A[p:q+1]#左边的数组暂存
    R = A[q+1:r+1]#右边的数组暂存
    L.append(inf)#插入哨兵
    R.append(inf)
    i = 0
    j = 0
    for k in range(p,r+1):#将数组合并到A中
        if L[i]<R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1

循环不变式为：

在for循环的每次迭代时，子数组 $A[p..k-1]$ 按从小到大的顺序包含 $L[1..n1+1]$ 和 $R[1..n2+1]$ 中的 $k-p$ 个最小元素，进而， $L[i]$ 和 $R[j]$ 是各自所在数组中未被复制回数组A的最小元素。
注:数组下标从1开始，n1,n2分别为L和R的长度

接下来我们证明这个循环不变式:
初始化:

在循环的第一次迭代之前，有 $k=p$ ,因此 $A[p..k-1]$ 为空，包含 $k-p=0$ 个最小元素，此时 $i=1,j=1$ ， $L[i]$ 和 $R[j]$ 是各自所在数组中未被复制回数组A的最小元素

保持：

为了理解每次迭代都维持循环不变式，我们先假设 $L[i]<=R[j]$ ，此时 $L[i]$ 是未被复制回数组A的最小元素。因为 $A[p..k-1]$ 包含k-p个最小元素，所以将 $L[i]$ 复制到A[k]之后，子数组 $A[p..k]$ 将包含 $k-p+1$ 个最小元素，更新k值和i值后，即维持了原来的不等式成立。

终止:

终止时 $k = r+1$ ,根据循环不变式 $A[p..k-1]$ 就是 $A[p..r]$ 且按照从小大大顺序包含L和R中的k-p个最小元素。
完整的归并排序python代码:

inf = float("inf")
def merge(A,p,q,r):
    L = A[p:q+1]
    R = A[q+1:r+1]
    L.append(inf)
    R.append(inf)
    i = 0
    j = 0
    for k in range(p,r+1):
        if L[i]<R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1
def mergeSort(A,lo,hi):
    if lo==hi:
        return
    mid = (lo+hi)//2
    mergeSort(A,lo,mid)
    mergeSort(A,mid+1,hi)
    merge(A,lo,mid,hi)

归并排序图示：

归并.jpg

2. 分析分治算法

我们可以用递归方程或递归式来描述递归分治算法的运行时间。
分治算法运行时间的递归式来自于基本模式的三个步骤，假设 $T(n)$ 是规模为n的一个问题的运行时间。
当问题规模足够小时，则将运行时间写作 $Θ(1)$ 。假设吧原问题分解成 $a$ 个子问题，每个子问题的规模是原问题的 $1/b$ ，求解 $a$ 个子问题就需要 $aT(n/b)$ 的时间。
如果分解成子问题需要时间 $D(n)$ ，合并时间为 $C(n)$ ，那么得到递归式