算法导论复习

标签：10 结点复习 int 导论问题算法最优例题

概论

重要特性 输入、输出、确定性、有限性

算法描述 自然语言、流程图、伪代码、程序代码

算法的复杂性 时间复杂性、空间复杂性

算法的渐进性态

O(g(n)) 上界

Ω(g(n)) 下界

Θ(g(n)) 确界

logn<n<nlogn<n2<n3<2n

NP完全理论 能在多项式时间内求解的判定性问题称为P问题，在多项式时间能验证猜测解的正确性为NP问题

递归与分治

递归概念

递归定义 用函数自身定义的函数 GNU is Not Unix

递归函数两个要素 边界条件与递归方程

满足条件 可转化（可以转化为一个或者多个子问题，子问题的求解方法与原问题完全相同，只在规模上不同）、调用次数有限、有结束递归的条件来终止递归，并不是所有递归都可以转换

何时使用递归 定义是递归的（斐波那契），数据结构是递归的（链表），问题的求解方法是递归的（汉诺塔，数的排列）

递归算法转化为非递归算法

直接转化法：直接用循环结构的算法替代递归算法，不需要使用栈
用栈模拟系统的运行过程，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法，需要使用栈

排列问题

Template<class type>
void Perm(Type list[], int k, int m)
{
//递归地产生所有前缀是list[0:k-1],且后缀是list[k:m]的全排列的所有
    if (k==m) { //只剩下一个元素
        for (int i=0;i<=m;i++) cout<<list[i];
        cout<<endl;
    }
    else//还有多个元素，递归产生后缀是list[k:m] 的全排列
    for(i=k;i<=m;i++) {
        Swap(list[k],list[i]);
        Perm(list,k+1,m);
        Swap(list[k],list[i]); //记得还原
    }
}

C++

整数划分

对于数据n，最大加数不大于m的划分个数记作q(n,m)

分治概念

设计思想 将一个难以直接解决的大问题，分割成一些规模较小的子问题，这些子问题互相独立且与原问题相同，从而递归地解子问题，将各个子问题的解合并得到原问题的解

适用问题 该问题可以分解为若干个规模较小的相同问题；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；该问题的规模缩小到一定的程度就可以容易地解决；利用该问题分解出的子问题的解可以合并为该问题的解

求解过程 分解、求解、合并

时间复杂性计算 扩展递归技术、递归树、主定理方法

*▲主定理方法* T(n)=aT(n/b)+f(n)，其中a≥1，b>1为常数，该方程描述了算法的执行时间，算法将规模为n的问题分解成a个子问题，每个子问题的大小为n/b。比较两个式子大小即可

二分搜索

问题描述 给定已按升序排好序的n个元素a[1:n]，现要在这n个元素中找出一特定元素x

代码

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

解释

指针left在什么情况下会超过right?

Left指针向左移动, right指针向右移动，如果一直没有找到结果，那么这两个指针最终会重叠，指向同一个位置。此时队列中只剩下一个元素。

此时，left=right；因此middle=left=right；

如果这个元素满足x==a[middle]，程序结束 return middle；

否则如果x>a[middle], left=middle+1后，left将位于right的右边；

否则如果x<a[middle], right=middle-1后，right将位于left的左边

大整数乘法

问题描述 XY是n位二进制整数，计算他们的乘积XY

Strassen乘法

问题描述 计算两个矩阵相乘的结果，分块矩阵计算

解释两个 n/2×n/2 的矩阵相加：一行需要n/2次加法，共有n/2行，因此，两个矩阵相加的复杂度为 n/2×n/2=n^2/4，四次矩阵相加的复杂度为 O(n^2)

改进算法 只需要七次乘法

改进

乘法：

加法：

棋盘覆盖

问题描述 2^k阶的棋盘中只有一个方格残缺，要求用L型骨牌覆盖残缺棋盘上的所有方格且任何2个L型骨牌不得重叠覆盖，用递推求解时间复杂度

解释测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1) ，覆盖4个残缺子棋盘（ 2^(k-1)阶）需四次递归调用，共需时间4T(k-1)

合并排序

问题描述 数组排序

temlplate  <class type>
void MergeSort(Type a[], int left, int right)
  {   if (1eft < right) //至少有2个元素
       {  
       int i = (left + right ) /2; //取中点
       MergeSort(a, 1eft, i)；
       MergeSort(a, i+1, right)；
       Merge(a, b, 1eft, i, right)；//从a合并到数组b  //这一步和下一步复杂度为O（n）
       copy(a, b, left, right);//复制回数组a
     }
 }    

//Merge（）：两部分合并时，每次比较两部分的第一个，把比较出来的那个拿出来放入b，下标++进行下一轮比较

真正的排序是在Merge（）中进行的

合并排序算法=拆+排（Merge）

不断地递归中，前面部分只能停止在拆的环节，要后面部分返回了才能进入排的环节

只有末端的排完成后，返回到上一层。而上一层的全部返回后，才能进入上一层的排

对于单个元素，不拆不排直接返回上一层

快速排序

问题描述 数组排序

//以第一个元素为基准点的快排
template <class Type>
void QuickSoft(Type a[], int p, int r) {
    if(p<r) {
        int q=Partition(a, p, r)
        //找到q的位置，q就是分区后基准下标
        //同时确保该位置右边的比基准元素大，左边的比基准元素小
        QuickSort(a, p, q-1); //对左半段排序
        QuickSoft(a, q+1, r); //对右半段排序
        }
     }
//异常：小的在基准右边，大的在基本左边
//找到异常并交换
//再走的过程中，i以左都是小于基准的。j以右都是大于基准的
int Partition(Type a[],int p , int r ) {
    int i = p; j = r+1;
    type x = a[p];//取出基准元素，并赋值给x
    while(true) { 
         while(a[++i] < x && i < r);//从左边开始看（正常的就继续循环往下走），直到找到一个异常，把i定位到这个异常
         while(a[--j] > x);//从右边开始看（正常的就继续循环往下走），直到找到一个异常，把j定位到这个异常
         if (i >= j) break;
    /*
    i和j相向而行，停止情况有两种
    一种是两者正好碰在一起，（i+1==j），即i就在j的左边。下一步++i，--j，两者都异常，此时j到了i的左边，就是i>j的情况
    （这一种是两者的下一步都异常，经过--后j落在了一个小于基准的数字上，为后面交换基准做了准备）
    另一种是最终二者碰到一个等于基准的数，i==j
    */
         swap(a[i],a[j]);//交换两个异常值，其都为正常（就是符合小的在基准左边，大的在基本右边）
    }
    swap(a[p], a[j]);//把基准放在中间
    return j;//最后j就是基准的位置
}

//随机选择基准点的快速排序
template <class Type>
void randomizedQuickSoft(Type a[], int p, int r) {
    if (p<r) {
        int q=randomizedPartition(a, p, r);//利用随机版partition求出q
        randomizedQuickSort(a, p, q-1); //对左半段排序
        randomizedQuickSoft(a, q+1, r); //对右半段排序
        }
}

template <class Type>
int randomizedPartition(Type a[], int p, int r) {
    int i=random(p, r);//找出一个随机位置
    swap(a[i], a[p]);//把该随机位置和第一个位置上元素交换，基准点就是随机的值。本质上都是第一个位置上的
    return Partition (a,p,r);
}

解释

步骤
- 分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任意一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]，下标q在划分过程中确定
- 递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序
- 合并
最坏情况，已经排好，O(n^2)
最好情况，每次划分大小都是n/2，O(nlogn)

线性时间选择

问题描述

无序排列中求n个元素中第k小的元素（主要求中位数）。

teplate <class Type>
Type RandomizedSelect (a[], int p,int r, int k) {
    if (p==r) return a[p];
    int i = RandomizedPartition(a, p, r), //前面有
    j = i-p+l  //统计前半部分元素个数j,  i为基准点
    if ( k <= j )
        return RandomizedSelect(a, p, i, k);
    else
        return RandomizedSelect(a, i+1, r, k-j);
}

解释

根据随机产生的基准点，将元素分为2组，基准点包含在第1组中；

如果k<=j，则第k小元素落在a段，为a段的第k小元素；

如果k>j，则a段的所有元素都比第k小元素还要小，第k小元素落在b段，为b段中的第k-j小元素（-j的含义是去掉a段的元素总个数）

最坏情况，分成两个1和n-1的子问题，O(n^2)

最好情况，每次都产生n/2大小的子问题，O(n)

基准点选择优化

例如可以分成五个组，取每组中位数的中位数。设所有元素互不相同。在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x,因此，找出的基准x至少比3(n-5)/10个元素大。同理，基准x也至少比3(n-5)/10个元素小。当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

Type Select(Type a[], int p, int r, int k) {
    if (r-p<75) {
        TO DO//用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
    for ( int i = 0; i<=(r-p-4)/5; i++ ) {
        //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
        Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
        int i=Partition(a,p,r, x),
        j=i-p+1;
        if (k<=j) return Select(a,p,i,k);
        else return Select(a,i+1,r,k-j);
    }
}

例题

a=[2,6,9,1,4,10,20,6,22,11,10,9,4,3,7,16,11,8,2,5,4,1]

寻找第5小元素

(要求两个中位数选择较小的一个，支点放在第一个列表中)

解答

，分组如下

[2,6,9,1,4] [10,20,6,22,11] [10,9,4,3,7] [16,11,8,2,5] [4,1]

中位数集合[4, 11, 7, 8, 4]，选择中位数的中位数为7作为支点

把支点放在第一个列表中

划分a[0:11]=[2, 6, 1, 4, 6, 4, 3, 2, 5, 4, 1, 7] a[12:21]=[9, 10, 20, 22, 11, 10, 9, 16, 11, 8]

对a[0:11]继续分组 [2,6,1,4,6],[4,3,2,5,4],[1]

中间元集合:[4,4,1]，中间元的中间元为4作为支点

把支点放在第一个列表中，划分：[2,1,4,4,3,2,4,1] [6,6,5]

对a[0:7]继续分组 [2,1,4,4,3],[2,4,1]

中间元集合:[3,2]，中间元的中间元为2作为支点

划分：[2,1,2,1] [4,4,3,4]

第一组小于5了

取第二组第5-4=1小的，也就是3

通过求中位数的中位数得到合理的基点，划分为大致的两部分

然后看k值落在哪一部分就保留哪一部分在里面找

最接近点对

一维情况

将S上的n个点分成大致相等的2个子集S1和S2
分别求S1和S2中的最接近点对
求一点在S1、另一点在S2中的最接近点对
从上述三对点中找距离最近的一对

二维情况

m为S中各点x间坐标的中位数，构造S1和S2 .S1,S2分别为分成的两部分 O(n)
递归求S1和S2的最小距离 2T(n/2)
求上述两个距离的最小值dm
设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；

P2是S2中距分割线l的距离在d之内所有点组成的集合；

将P1和P2中的点依其y坐标值排序；并设X和Y是相应的已排好序的点列 O(nlogn)
通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离； O(n)
选择dm dl的最小值

中位线上的归于左边

循环赛日程表

问题描述 设有n(n = 2^k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天必须比赛一场，不能轮空。

发现规律

动态规划

概念

基本思想 基本思想是在对一个多阶段决策的问题，按照某一顺序，根据每一步所选决策的不同，会引起状态的转移，最后会在变化的状态中获取到一个决策序列。

基本要素

最优子结构性质（分析问题是否满足最优性原理（用反证法）：①先假设由问题的最优解导出的子问题的解不是最优的；②再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾）
子问题重叠性质（子问题不相互独立，重复出现，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解）

算法步骤

分析最优解的性质，并刻画其结构特征；
递归地定义最优值；
以自底向上或自顶向下的方式计算出最优值；
根据递归计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解。

矩阵连乘

问题描述 每计算出一个元素，需要q次乘法，最终得到的矩阵是p×r矩阵，有p×r个元素，因此，计算C需要的乘法次数为q×p×r。每次要选择较小的q×p×r。给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，且i=1,2⋯,n-1,如何确定计算矩阵连乘积的计算次序，使得计算矩阵连乘的数乘次数最少。

解释矩阵连乘积从Ai到Aj定义为A[i:j]，A[i:j]最少的乘法次数定义为m[i,j]，最优断开位置k记为

标签：10,结点,复习,int,导论,问题,算法,最优,例题
From： https://blog.csdn.net/weixin_57014764/article/details/144912514

概论