算法考试大纲

教材：

1577967550456.png

1、计算复杂度

一、定义

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度。记作：T(n)=O(f(n))。它表示随问题n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中，f(n)是问题规模n的某个函数。

二、两种方法

取对数后阶乘的复杂度等于$nlogn$

只写结果不给分

==共12分==

2、快速排序或者合并排序

两种排序的过程、优劣、时空复杂度

一、合并排序

1. 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

2. 代码：

   1. public static void **mergeSort**(Comparable a[], int left, int right)
   
        {
   
         **if** (left<right) {//至少有2个元素
   
         int i=(left+right)/2; //取中点
   
         **mergeSort**(a, left, i);
   
         **mergeSort**(a, i+1, right);
   
         **merge**(a, b, left, i, right); //合并到数组b
   
         **copy**(a, b, left, right);  //复制回数组a
   
         }
   
        }
   
   3. 
   

1577982324939.png

4. &最坏时间复杂度：****O(****nlogn****)

   &平均时间复杂度：****O(****nlogn****)

   &辅助空间：****O(n)

   &稳定性：稳定

二、快速排序

1. 算法思想：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

2. 代码：

   Void QuickSort(Type a[], int i, int j)
   { if (i<j){   int p=partition(a, i, j);
                  QuickSort(a, i, p-1);
                QuickSort(a, p+1, j); }
   }
   int partition (Type a[], int i, int j)
      {  x = a[i];
         // 将<= x的元素交换到左边区域
         // 将>= x的元素交换到右边区域
         while (i<j) {
           while (i<j&&a[j]>=x) --j;
    a[i]↔a[j];
           while (i<j&&a[i]<=x) ++i;
    a[i]↔a[j];
       }
        return i;
      }
   

3. 复杂度分析

1577982679875.png

1577982744663.png

==共15分==

3、最长公共子序列、链表

要写详细过程

一、最长公共子序列

1.定义

• 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

• 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

• 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

2.结构

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则

(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。

(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。

(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。

3.性质

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

4.子问题的递归问题

1577983674236.png

5.计算最优值

由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

Algorithm lcsLength(x,y,b)
1: m<-x.length-1;
2: n<-y.length-1;
3: c[i][0]=0; c[0][i]=0;
4: for (int i = 1; i <= m; i++)
5:    for (int j = 1; j <= n; j++) 
6:       if (x[i]==y[j]) 
7:           c[i][j]=c[i-1][j-1]+1;
8:           b[i][j]=1;
9:        else if (c[i-1][j]>=c[i][j-1]) 
10:          c[i][j]=c[i-1][j];
11:          b[i][j]=2;
12:      else 
13:           c[i][j]=c[i][j-1];
14:           b[i][j]=3;

//构造最长公共子序列
Algorithm lcs(int i,int j,char [] x,int [][] b)
   {
      if (i ==0 || j==0) return;
      if (b[i][j]== 1){
        lcs(i-1,j-1,x,b);
        System.out.print(x[i]);
        }
      else if (b[i][j]== 2) lcs(i-1,j,x,b);
        else lcs(i,j-1,x,b);
   }

二、链表

==共18分==

4、回溯法

一、概念

• 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

• 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

• 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

二、相关概念

• ±状态空间树****(****Solution Space Tree****)****：****解空间的树结构称为解空间树****.

三、基本思想

• 搜索：回溯法从根结点出发，按深度优先策略遍历解空间树，搜索满足约束条件的解。

• 剪枝：在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界;也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。

四、小结

(1) 适应于求解组合搜索问题（含组合优化问题）

(2) 求解条件：满足多米诺性质

(3) 解的表示：解向量，求解是不断扩充解向量的过程

(4) 回溯条件：

搜索问题-****约束条件

优化问题-****约束条件****+****代价函数

(5) 算法复杂性：最坏情况为指数，空间代价小

(6)****降低时间复杂性的主要途径：

利用对称性裁减子树

划分成子问题

(7) 分支策略（深度优先、宽度优先、宽深结合、优先函数）

==共20分==

5、单纯形法

一、概念

一般线性规划问题中当线性方程组的变量数大于方程个数，这时会有不定数量的解，而单纯形法是求解线性规划问题的通用方法。

具体步骤是，从线性方程组找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小了，决定下一步选择的单纯形。通过优化迭代，直到目标函数实现最大或最小值。 [1]

换而言之，单纯形法就是秉承“保证每一次迭代比前一次更优”的基本思想：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进后更优的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解，也可用此法判别。

二、过程

单纯形法的一般解题步骤可归纳如下：

①把线性规划问题的约束方程组表达成典范型方程组，典范型方程组要实现变量转换（所有变量为非负）、目标转换（统一为求极大值，若求极小值可乘以(-1)）、约束转换（由不等式转化为等式）。然后，找出基本可行解作为初始基可行解。列出初始单纯形表。

②若基本可行解不存在，即约束条件有矛盾，则问题无解。

③若基本可行解存在，从初始基可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

image.png

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。如今一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

==共20分==

6、解答题（选自第九章）

==共15分==

分支限界

分支限界

一、基本思想

•分支限界法由“分支”策略和“限界”策略两部分组成。“分支”体现在对问题空间是按广度优先搜索；“限界”策略是为了加速搜索速度而采用启发式剪枝的策略。

•分支搜索法采用广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树的策略，依次生成E结点所有分支(即所有的子结点)。

•在生成的结点中，将采用更有效的约束函数(限界函数)控制搜索路径，去除那些不满足约束条件(即不可能导出最优解)的结点，使之能更好地朝着状态空间树上有最优解的分支推进。

二、过程

• 分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界。

• 按广度优先策略遍历问题的解空间树：

• 在当前E结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值。

• 如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入活结点表中。

• 再依次从活表中选取使目标函数的值取得极值的结点成为当前E结点。

• 重复上述过程，直到找到最优解。

三、常见的两种分支限界方法

一、FIFO式分支限界法：

按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。

• 初始，根结点是唯一的活结点，根结点入队。

• 从活结点队中取出根结点后，作为当前E结点。对当前E结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。

• 重复上述过程：再从活结点表中取出队首结点（队中最先进来的结点）为当前E结点，……；直到找到一个解或活结点队列为空为止。

二、优先队列式分支限界法：

按照优先队列中规定的优先级选取优先级最高的结点成为扩展结点。

• 对每一活结点计算一个优先级,并根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

算法

一、什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

二、算法的特征

1. 有穷性(Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

2. 确切性(Definiteness)

算法的每一步骤必须有确切的定义；

3. 输入(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

4. 输出(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5. 可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。