算法分析与设计复习-第一、二章

1. 什么是算法

算法是由若干条指令组成的有穷序列,满足以下4条性质

• 输入:有零个或者多个由外部提供的量作为算法的输入
• 输出:算法产生至少一个量作为输出
• 确定性:组成算法的每条指令都是清晰的,无歧义的
• 有限性:算法中每条指令的执行次数都是有限的,执行每条指令的时间也是有限的。

而程序是算法用某种程序设计语言的具体实现,程序可以不满足有限性的性质。

2. 算法复杂度分析

如果分别用N(要解决的问题规模)、I(算法的输入)、A(算法的本身)、C(复杂性),那么就有C=F(N,I,A)是一个由N、I、A确定的三元函数。

通常还将复杂性细粒度为时间复杂度和空间复杂度,而算法本身隐含在复杂性函数名中,因此将T和S分别简写为

T = T(N,I)、S = S(N,I)

同时我们有一些规则

对于基本的操作,例如运算,赋值,比较,这些基本操作的的代价均为1

这个操作是为了统一机器的性能,算法的运行时间依赖于问题输入规模与实例

对于相同的输入规模,实例将会影响运行,主要体现为最好情况(不常出现)、最坏情况(确定上界,更具一般性)、一般情况

渐进分析:忽略T(n)的系数与低阶项,仅关注高阶项,用记号O进行表示

理解:存在x>0{c1,c2,n0},使得对于任意的一点{n0},在这个n0之后,Tn始终是在c1g(n)和c2g(n)之间的

这道题的分析思路是找到一个数:7/2(n)-4>=0，解得n>=8/7,由于求解渐进紧确界的{n0}仅是要求存在这样的一个{n0},因此我们不妨令{n0=2}

当{n>=n0=2}的时候,有7/2(n)-4>=0,因此在这种情况下原式>=3/2(n^2)>=n^2 ,在这样的情况下,我们求得了其一个下界是{n^2}

我们继续考察式子,我们希望上界也是(n^2)的表达式,考察式子,首项是{3/2n^2},第二项是{2/7n},我们可以将第二项乘上一个{n},最后一项{-4},可以去掉,也可以写为{n^2}

在这时候,我们就可以写出

存在,c1=1,c2=6,n0=2,使得所有的n>={n0},c1n^2<=T(n)<=c2n^2

简单来说就是一直在T(n)之上的一个cg(n)表达式

2.1 递归的概念

直接或者间接调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

2.2 分治法的基本思想

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,递归地分解这些子问题,然后将各子问题的解合并得到原问题的解。

void devide_and_conquer(P){
    if(|P|<=n0){
        adhoc(P);//基本子算法,base-case
    }
    divide P into smaller subinstances P1,P2,...,Pk;
    for(int i = 1;i<=k;i++){
        yi = divide_and_conquer(Pi);
    }
    return merge(y1,y2,...,yk);
}

2.3 二分搜索技术

二分搜索算法是运用分治策略的典型例子，给定已经排好序的n个元素a[0,n-1],现在在这n个元素中要找出一个特定元素x,二分搜索算法充分利用了元素间的次序关系,采用分治策略,可在最坏情况下用O(logn)时间完成搜索任务。二分搜索的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与x作比较,如果x=a[n/2],则找到x,算法终止,否则当x<a[n/2],那么就只在数组a的左边继续搜索x,如果x>a[n/2],则只在数组a的右半部分继续搜索x

int binarySerach(Type a[],const Type& x,int n){
    int left = 0;
    int right = n-1;
    //搜索区间,闭区间[0,n-1]
    while(left <= right){
        int middle = (left+right)/2;
        if(x == a[middle]){
            return x;
        }else if(x < a[middle]){
            right = middle-1;
        }else if(x > a[middle]){
            left = middle+1;
        }
    }
    return -1;
}

2.6 棋盘覆盖问题

问题描述,在一个2^k*2^k个方格组成的棋盘中,恰有一个方格与其他方格不同,则称该方格为一个特殊方块,而且把这个棋盘叫做为一个特殊棋盘.

对于这个问题,我们可以思考这个问题在什么样的情况下有解?

对于base-case,我们令k=1,也就是一个2*2的棋盘

我们发现无论如何这个棋盘都能找到一种方式使得棋盘恰好被填满,因此归纳奠基成立

我们假设n=k的时候,也就是2^k*2^k的时候,这个问题是有解的(解的形式不确定,需要通过后面的递推进行确定)

那么当n=k+1的时候,也就是一个2^k+1*2^k+1的棋盘上,我们利用假设的条件,进行递推,判断是否有解,过程如下:

如图所示,我们将k+1的棋盘划分为了4个k大小的棋盘,根据初始条件,我们不妨假设右上角中存在特方格,由于我们假设k大小的特殊棋盘是有解的,那么问题就来了,剩下的3个棋盘怎么办呢?如果想要用上我们假设的k大小的棋盘能够有解,我们必须要保证

• 棋盘的大小是k
• 有特殊方格

由于骨牌的形状是L,它恰能够在初始条件下,在其余的个棋盘上安插3个方格,这样,我们就构造出来了3个具有特殊方格的特殊的k大小的特殊棋盘,根据假设,它们在这种情况下是有解的,因此,递推成立。

最终结论就是:因为当n=k的时候是有解的,所以n=k+1的时候也是有解的,而k又是任意的,所以这个结论在k>=1呃的时候都成立了。

下面来看看代码是如何编写的

#include <iostream>
using namespace std;
int title = 0;
const int N = 1000+5;
int board[N][N];
/**
 * 递归思路,通过左上角的坐标唯一确定棋盘和特殊方块的位置从而确定这次递归要处理的是哪一个棋盘
 * 特殊方块的位置是为决策提供位置
 * @param tr:棋盘左上角的行号(row)
 * @param tc:棋盘左上角的列号(col)
 * @param dr:特殊方块的行号
 * @param dc:特殊方块的列号
 * @param size
 */
void chessBoard(int tr,int tc,int dr,int dc,int size){
    if(size == 1){//棋盘的大小,如果前的大小是1的时候,那么我都不用放骨牌了
        return ;
    }
    int t = title++;
    int s = size /2;
    //判断左上角是否是特殊棋盘
    if(dr < tr+s && dc < tc+s){
        chessBoard(tr,tc,dr,dc,s);//是特殊棋盘,那么左上角的这一个棋盘划分为4个子棋盘
    }else{
        //如果不是特殊棋盘,那么就要求覆盖左上角,而且按照算法的定义是放在交界处的(边界,也就是在之内)
        board[tr+s-1][tc+s-1] = t;
        //继续划分左上角的棋盘
        chessBoard(tr,tc,tr+s-1,tc+s-1,s);
    }
    //判断右上角
    if(dr < tr+s && dc >= tc+s){
        chessBoard(tr,tc+s,dr,dc,s);
    }else{
        board[tr+s-1][tc+s] = t;
        chessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }
    //判断左下角
    if(dr>=tr+s && dc < tc+s){
        chessBoard(tr+s,tc,dr,dc,s);
    }else{
        board[tr+s][tc+s-1] = t;
        chessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }
    //判断右下角
    if(dr >= tr+s && dc >= tc+s){
        chessBoard(tr+s,tc+s,dr,dc,s);
    }else{
        board[tr+s][tc+s] = t;
        chessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}

int main(){
    chessBoard(0,0,3,3,8);
    for(int i = 0;i<8;i++){
        for(int j = 0;j<8;j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
}

解析时间复杂度

2.7 归并排序

归并排序是用分治策略实现对n个元素进行排序的算法,其基本思想就是:将待排序的元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成于要求的排好序的集合

递归算法可以描述如下

void mergeSort(int a[],int left,int right){
    //当left==right的时候,这时候有且仅有一个元素,这时候数组天然有序,返回到上一层合并排序中
    //对天然有序的数组进行排序
    if(left<=ight){
        int i = (left+right)/2;
        mergeSort(a,left,i);//对[left,i]内的元素进行排序
        mergeSort(a,i+1,right);//对[i+1,right]内的元素进行排序
        merge(a,b,left,i,right);//合并到数组b
        copy(a,b,left,right);//复制到数组a
    }
}

MergeSort的递归过程只是将待排序集合一分为二,直到待排序集合只剩下一个元素为止,然后不断合并两个排好序的数组段。

#include <iostream>
using namespace std;
//将数组a中已经排好序的ll~lr和已经排好序的rl~rr合并起来
void merge(int a[],int ll,int lr,int rl,int rr){
    //排序的逻辑是这样的,两个指针分别指向排好序的两端的起点
    //然后依次比较两个指针下指的值
    //1.计算出长度
    int lLen  = lr-ll+1;
    int rLen  = rr-rl+1;
    int *merge_a = new int[lLen+rLen];
    //2.指针指向起点
    int  i = ll;
    int  j = rl;
    int  k = ll;
    while (i<= lr&& j <= rr){
        if(a[i] <= a[j]){
            merge_a[k++] = a[i++];
        }else{
            merge_a[k++] = a[j++];
        }
    }
    //处理剩下的
    while (j<=rr){
        merge_a[k++] = a[j++];
    }
    while (i<=lr){
        merge_a[k++] = a[i++];
    }
    //最终我们再合并数组a
    //copy
    k=0;
    while (k<lLen+rLen){
        a[ll+k] = merge_a[k++];
    }
    delete[] merge_a;
}

void mergeSort(int a[],int l,int r){
    if(l<r){
        int mid = (l+r)/2;
        mergeSort(a,l,mid);
        mergeSort(a,mid+1,r);
        //把两端拍好序的数组,变成一个更大的排好序的数组
        merge(a,l,mid,mid+1,r);
    }
}

这是一个为了理解大致算法思路而写出来的程序,下面我们来看看就接下来看看看书本上消除递归之后的合并排序算法

void merge(int c[],int d[],int l,int m,int r){//合并c[l:m]和c[m+1,r]到d[l:r]
    int i = l,j=m+1,k=l;
    while ((i<=m) && (j<=r)){
        if(c[i]<= c[j]){
            d[k++] = c[i++];
        }else{
            d[k++] = c[j++];
        }
    }
    if(i>m){
        for(int q = j;q<=r;q++){
            d[k++] = c[q];
        }
    }else if(j>r){
        for(int q = i;q<=m;q++){
            d[k++] = c[q];
        }
    }
}

void mergePass(int x[],int y[],int s,int n){//合并大小为s的相邻子数组
    int i = 0;
    //就这样想,s是一个子数组的长度,2*s就是两个子数组的长度
    //那么这个n-2*s是什么意思呢?
    //就是这个数组能划分为几个这样的相邻子数组,如果剩下的元素不能划分为这样的子数组,我们就不划分,按照特例处理
    while(i<= n- 2*s){
        merge(x,y,i,i+s-1,i+2*s-1);
        i = i+2*s;//完成该段的合并
    }
    //如果剩下的元素是小于2s的,按照特例处理
    //如果剩下的元素个数是多于s个,但是小于2s个
    //这里怎么理解?
    //我们从递归函数的定义入手
    //我们要做的是:x是源数组,我们希望将x分成若干个s段的子数组,对于这若干个相邻的子数组进行合并
    //合并到y中,这样的话y的话就是有序的了
    //那么对于不满足能够分成最小规模的2个s段的子数组,分为以下两种情况
    //有一个子数组能够到s个元素,另一个子数组不能到s个元素,这时候可以执行合并
    //剩下的子数组不能到s个元素,这时候不能执行合并,因为我们规定的递归函数有一个关键的参数
    //就是mid(子数组的分界点),如果我们传入一个l+s>=n,那么也就是说分不成两个数组
    //这时候就没办法按照定义去执行我们的merge()函数,这时候,我们直接保留这不足s个元素的状态到y中
    //等待其他长度的归并的时候,再做处理即可
    if(i+s<n){
        //然后就是不相等的元素个数之间进行合并
        //i~i+s-1这个区间,i+s~n-1这个区间合并起来
        merge(x,y,i,i+s-1,n-1);
    }else{//i+s>=n,剩下的元素是少于s个的
        for(int j = i;j<=n-1;j++){
            y[j] = x[j];
        }
    }
}

void mergeSort(int a[],int n){
    int *b = new int[n];
    int s = 1;
    while (s < n){
        //轮流交替,O(n)空间复杂度
        mergePass(a,b,s,n);
        s+=s;
        mergePass(b,a,s,n);
        s+=s;
    }
}

关于复杂性分析

2.8 快速排序

快速排序算法是基于分治策略的另一个排序算法,其基本思想是:对于输入的子数组a[p:r],按照以下三个步骤进行排序

• 分解:以a[p]为基准元素将a[p:r]划分为三段a[p:q-1],a[q],a[q+1,r]使得a[p:q-1]中任何一个元素小于等于a[q],而a[q+1:r]中任意一个都大于等于a[q]
• 递归求解:通过递归调用快速排序算法,分别对a[p:q-1]和a[q+1,r]进行快速排序
• 合并:merge,由于对a[p,q-1]和a[q+1,r]的排序是原地进行的,因此对a[p,q-1]和a[q+1,r]都已经排好序之后,不需要执行任何的计算,a[p:r]就已经是排好序的了。

int partition(int a[],int p,int r){
    int i = p;
    int j = r+1;
    int x = a[i];
    //将小于x的元素交换到左边的区域,将大于x的元素交换到右边的区域
    while(true){
        //我们的目的是找出那些应该在[p:i]之内的,但是跑到了[j,r]之内的元素
        while (a[++i] <x  &&  i<r);//自旋,从左边开始找,一直找到有一个数,这个数是大于x的
        while (a[--j] >x  &&  j>p);//自旋,从右边开始找,一直找到有一个数,这个数是小于x的
        if(i >= j){//证明都排好序了,这时候同样满足的是a[i]>=x>=a[j],但是通过下标的关系可以看出,它们都已经归位了
            break;
        }
        //否则就是还没有归位,我们交换它的位置
        swap(a[i],a[j]);//然后下一轮循环
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}

void quickSort(int a[],int p,int r){
    if(p<r){
        int j = partition(a,p,r);
        quickSort(a,p,j-1);
        quickSort(a,j+1,r);
    }
}

//随机选取主元
int randomizedPartition(int a[],int p,int r){
    int i = RANDOM();
    swap(a[i],a[i]);
    return partition(a,p,r);
}