软考：软件设计师 — 14.算法基础

十四. 算法基础

1. 算法的特性

算法是对特定问题求解步骤的描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

有穷性：执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义，无二义性。
可行性（有效性）：算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如 a=0，b/a 就无效。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

2. 时间复杂度与空间复杂度

时间复杂度是指程序运行从开始到结束所需要的时间。

通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模 n 的某个函数 T(n)。由于许多情况下要精确计算 T(n) 是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：

如果存在两个常数 c 和 m，对于所有的 n，当 n≥m 时有 f(n)≤cg(n)，则有 f(n) = O(g(n))。也就是说，随着 n 的增大，f(n) 渐进地不大于 g(n)。例如，一个程序的实际执行时间为 $T(n)=3n^{3}+2n^{2}+n$ ，则 T(n) = O( $n^{3}$ )。也可表示为 $\Omega \Theta$ 。

常见的对算法执行所需时间的度量：

O(1)<O( $log_{2}n$ )<O(n)<O( $nlog_{2}n$ )<O( $n^{2}$ )<O( $n^{3}$ )<O( $2^{n}$ )

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。

一个算法的空间复杂度只考虑在运行过程为为局部变量分配的存储空间的大小。

时间复杂度总结：

① 常数级时间复杂度 O(1)

单个语句

如：k = 0；

整个程序都没有循环语句，或复杂函数的调用

void main(){
  char*x = "ABCADAB";
  int m = strlen(x);
  printf("len:%d\n",m);
}

② 时间复杂度 O(n)

单层循环

void main(){
  int i,j;
  k = 0;
  for(i=0; i<n; i++){
    b[i]=0;
  }
}

③ 时间复杂度 O( $n^{2}$ )

双层循环（嵌套）

void main(){
  int i, s=0, n=1000;
  for(i=1; i<n; i++)
    for(j=1; j<n; j++)
    s+=j;
  printf("结果为："%d,s)
}

④ 时间复杂度 O( $n^{3}$ )

三层嵌套循环

如果循环不嵌套，则时间复杂度仍为 O(n)。

⑤ 时间复杂度 O( $log_{2}n$ )

// 二分查找
int search(int array[], int n, int v)
{
   int left,right,middle;
   left = 0,right = n-1;
   while(left <= right)
   {
     middle = (left+right)/2;
     if(array[middle]>v)
     {
       right = middle-1;
     }
     else if(array[middle]<v)
     {
       left = middle+1;
     }
     else
     {
       return middle;
     }
   }
   return =1;
}

如果再加一个 for 循环，那么时间复杂度就会变成 O( $nlog_{2}n$ )。

⑥ 时间复杂度 O( $nlog_{2}n$ )

典型代表：堆排序，每次重建堆的时间复杂度是 $log_{2}n$ ，n 个元素就是 $nlog_{2}n$ 。

⑦ 时间复杂度 O( $2^{n}$ )

典型代表：LCS最长公共子序列、钢管切割问题，动态规划法自顶向下，时间复杂度为 O( $2^{n}$ )。

例题1：

根据渐进分析，表达式序列： $n^{4}$ ，lgn， $2^{n}$ ，1000n， $n^{\frac{2}{3}}$ ，n！从低到高排序为（）。

A.lgn，1000n， $n^{\frac{2}{3}}$ ， $n^{4}$ ，n！， $2^{n}$

B. $n^{\frac{2}{3}}$ ，1000n，lgn， $n^{4}$ ，n！， $2^{n}$

C.lgn，1000n， $n^{\frac{2}{3}}$ ， $2^{n}$ ， $n^{4}$ ，n！

D.lgn， $n^{\frac{2}{3}}$ ，1000n， $n^{4}$ ， $2^{n}$ ，n！

解析1：

可以理解成对时间复杂度的比较，根据 O(1)<O( $log_{2}n$ )<O(n)<O( $nlog_{2}n$ )<O( $n^{2}$ )<O( $n^{3}$ )<O( $2^{n}$ )可得，lgn < $n^{\frac{2}{3}}$ < 1000n < $n^{4}$ < $2^{n}$ ，只有 D 项满足要求，因此选 D。

例题2：

已知算法 A 的运行时间函数为 T(n)=8T( $\frac{n}{2}$ )+ $n^{2}$ ，其中 n 表示问题的规模，则该算法的时间复杂度为（）。另已知算法 B 的运行时间函数为 T(n)=XT( $\frac{n}{4}$ )+ $n^{2}$ ，其中 n 表示问题的规模。对充分大的 n，若要算法 B 比算法 A 快，则 X 的最大值为（）。

A.Θ(n) B.Θ(nlgn) C.Θ( $n^{2}$ ) D.Θ( $n^{3}$ )

A.15 B.17 C.63 D.65

解析2：

根据主定理

f(n) = $n^{2}$ ，a = 8，b = 2，则 $log_{b}a$ = 3。显然满足第一条，f(n)< $n^{log_{b}a}$ ，即 $n^{2}$ < $n^{3}$ ，且 $\varepsilon$ = 1，所以 T(n) = Θ( $n^{log_{b}a}$ ) = Θ( $n^{3}$ )，第一个空选 D。第二个空求算法 B 比 A 快时 X 需要满足的条件，算法 B 中，f(n) = $n^{2}$ ，a = X，b = 4，则 $log_{b}a$ = $log_{4}X$ 。若满足第一条，则 T(n) = Θ( $n^{log_{b}a}$ )，因为要比算法 A 快，所以 T(n) 需要小于 $n^{3}$ ，n 越小才代表越快，因此 $log_{4}X$ < 3，所以 X < 64，X 可以为 63。如果满足第二条，则 T(n) = Θ( $n^{log_{b}a}$ logn)，那么 $log_{4}X$ 至少需要小于 2，T(n) 才会小于 $n^{3}$ ，所以 X < 16，X 也可以为 15。同理，如果满足第三条，那么 T(n) = $n^{2}$ ，且 $n^{2}$ > $n^{log_{b}a}$ ，能够求得 a 是小于 15 的。综合来看，X 的最大值是 63，也可以取到 15。因此选 C。

例题3：

求解两个长度为 n 的序列 X 和 Y 的一个最长公共子序列（如序列 ABCBDAB 和 BDCABA 的一个最长公共子序列为 BCBA）可以采用多种计算方法。如可以采用蛮力法，对 X 的每一个子序列，判断其是否也是 Y 的子序列，最后求出最长的即可，该方法的时间复杂度为（）。经分析发现该问题具有最优子结构，可以定义序列长度分别为 i 和 j 的两个序列 X 和 Y 的最长公共子序列的长度为 C[i,j]，如下所示。采用自底向上的方法实现该算法，则时间复杂度为（）。

A.O( $n^{2}$ ) B.O( $n^{2}$ lgn) C.O( $n^{3}$ ) D.O(n $2^{n}$ )

解析3：

若采用蛮力法，将 X 的每个子序列与 Y 进行比较，X 的子序列有 $2^{n}$ 个，因为每个字符都有存在在序列中和不存在两种情况，长度为 n，所以共有 $2^{n}$ 个子序列。和 Y 进行对比，Y 的长度也为 n，相当于两层嵌套过程，一层判断 X 的子序列，一层判断提取的子序列与 Y 是否相同，因此时间复杂度为 O(n $2^{n}$ )。对于优化的结构，采用自底向上的方式实现，即从 0 开始判断，式子中给出的是二维数组 C[i,j]，因此至少需要两层嵌套循环，因此时间复杂度为 O( $n^{2}$ )。因此选择 DA。

3. 常见算法策略

（1）算法策略概述

常见算法特征总结

分治法（主要是二分）

特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。

经典问题：斐波那契数列、归并排序、快速排序、二分搜索、矩阵乘法、大整数乘法等

贪心法（一般用于求满意解）

特征：局部最优，但整体不见得最优。每步有明确的、既定的策略。

经典问题：背包问题（如装箱）、多机调度、找零钱问题。

动态规划法（用于求最优解）

特征：划分子问题，并把子问题结果适用数组存储，利用查询子问题结果构造最终问题结果。（一般自顶向下时间复杂度为 O( $2^{n}$ )，自底向上时间复杂度为 O( $n^{a}$ )，后者效率更高）

经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列

回溯法

特征：系统搜索一个问题的所有解或任一解。

经典问题：N皇后问题、迷宫、背包问题

算法名称	关键点	特征	典型问题
分治法	递归技术	把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。	归并排序、快速排序、二分搜索
贪心法	一般用于求满意解，特殊情况可求最优解（部分背包）	局部最优，但整体不一定最优。每步有明确的、既定的策略。	背包问题（如装箱）、多机调度、找零钱问题
动态规划法	最优子结构和递归式	划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。	矩阵乘法、背包问题、LCS最长公共子序列
回溯法	探索和回退	系统搜索一个问题的所有解或任一解。有试探和回退的过程。	N皇后问题、迷宫、背包问题

算法策略判断：

回溯：有尝试探索和回退的过程。
分治：分治和动态规划比较难区分。分治不好解决问题，从而记录中间解解决问题。分治主要采用二分的思想，二分以外都用动态规划法解决了。二分的时间复杂度与 O(nlog2n) 相关，需注意有无外层嵌套循环，如果有，则需要再乘 n。（结合归并排序、快速排序的过程，也是二分的）
动态规划法：有递归式，自底向上实现时，中间解基本上查表可得，时间复杂度一般是 O( $n^{a}$ )，具体 a 的值取决于 for 循环的嵌套层数。如果循环变量从 0 或 1 开始，到 n 结束，这种情况就是从小规模到大规模，自底向上。如果自顶向下，时间复杂度为 O( $2^{n}$ )，和分治的实现就差不多了，查表的意义可以忽略不记，循环变量一般由 n 开始，向 1 缩小，是从大规模到小规模。
贪心法：有时也会出现最优子结构的描述，但没有递归式。考虑的是当前最优，求得的是满意解。

（2）分治法

对于一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n 较小）则直接解决；否则将其分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归地解决这些子问题，然后将子问题的解合并得到原问题的解。

该问题的规模缩小到一定的程度就可以容易地解决（分解）
该问题可以分解为若干个规模较小的相同问题（解决）
利用该问题分解出的子问题的解可以合并为该问题的解（合并）
该问题所分解出的各个子问题是相互独立的

递归就是在运行过程中调用自己。

斐波那契数列

int F(int n)
{
  if(n==0) return 1;
  if(n==1) return 1;
  if(n>1)  retrun F(n-1)+F(n-2);
}

自顶向下：n -> n-1 -> n-2 -> … -> 2 -> 1

自底向上：1 -> 2 -> 3 -> … -> n-1 -> n

二分查找

function Binary_Search(L,a,b,x){
  if(a>b) return -1;
  else{
     m=(a+b)/2;
     if(x==L[m]) return(m);
     else if(x>L[m])
        return(Binary_Search(L,m+1,b,x)); // x 在中间值右侧
     else
        return(Binary_Search(L,a,m-1,x)); // x 在中间值左侧
      }
}

（3）贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但可能得不到最优解。（贪心法解决部分背包问题可得最优解）

在贪心思想中，优先放置单位价值大的物品，即用小空间放大价值物品，物品 1 2 3 的单位价值分别是 7 6 5，因此在 0-1背包问题中，由于物品无法分割，因此最优解是放置价值 380 的物品。部分背包问题，物品可以分割，因此可以将物品 1 2 放置后，再放置单位价值最低的物品 3 的一部分，得到价值 420 的物品，此时也是最优解，所以贪心法解决部分背包问题可以得到最优解。

例题1：

采用贪心算法保证能求得最优解的问题是（）。

A.0-1背包 B.矩阵链乘 C.最长公共子序列 D.部分（分数）背包

解析1：

贪心算法解决部分背包问题可以得到最优解，所以选 D。

例题2：

现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动 A 从 1 时间开始，5 时间结束，活动 B 从 5 时间开始，8 时间结束，则活动 AB 不冲突。现需计算 n 个活动需要的最少场地数。

求解该问题的基本思路如下（假设需要场地数为 m，活动数为 n，场地集合为 P1,P2,…,Pm），初始条件 Pi 均无活动安排：

采用快速排序算法对 n 个活动的开始时间从小到大排序，得到活动 a1,a2,…,an。对每个活动 ai，i 从 1 到 n，重复步骤 2、3、4；
从 P1 开始，判断 ai 与 P1 的最后一个活动是否冲突，若冲突，考虑下一个场地 P2, …；
一旦发现 ai 与某个 Pj 的最后一个活动不冲突，则将 ai 安排到 Pj，考虑下一个活动；
若 ai 与所有已安排活动的 Pj 的最后一个活动均冲突，则将 ai 安排到一个新的场地，考虑下一个活动；
将 n 减去没有安排活动的场地数即可得到所用的最少场地数。

该问题首先采用了快速排序算法进行排序，其算法设计策略是（）；后面步骤采用的算法设计策略是（）。整个算法的时间复杂度是（）。下表给出了 n=11 的活动集合，根据上述算法，得到最少的场地数为（）。

i	1	2	3	4	5	6	7	8	9	10	11
开始时间	0	1	2	3	3	5	5	6	8	8	12
结束时间	6	4	13	5	8	7	9	10	11	12	14

A.分治 B.动态规划 C.贪心 D.回溯

A.Θ(lgn) B.Θ(n) C.Θ(nlgn) D.Θ( $n^{2}$ )

A.4 B.5 C.6 D.7

解析2：

快速排序的算法设计策略是分治的思想；该问题在第 2、3、4 步采用的是贪心的策略，即将当前的活动放到与场地中最后一个活动不冲突的场地中，并且后面的算法中没有涉及到递归式，因此不会是动态规划，没有二分的思想，也不会是分治，也没有回退与探索，也不是回溯；在整个算法中，涉及到对活动 ai 的遍历以及对场地 Pj 的遍历，所以需要两层嵌套循环，因此时间复杂度是 $n^{2}$ ；在实例中，n=11，可以得到如下计算过程：活动1 [0,6]，时间 6 结束，放到场地 1 中；活动2 [1,4]，时间 4 结束，与场地 1 中的最后一个活动 1 的结束时间冲突，因此活动2 放到新的场地 2 中；同理，活动3 [2,13] 的开始时间与场地 1、2 中的活动均冲突，因此活动3 放到新的场地 3 中；同理，活动4 [3,5] 放到场地 4 中；活动5 [3,8] 放到场地 5 中；活动6 [5,7] 的开始时间是 5，此时活动2 在时间 4 时结束，因此活动6 可以放到场地 2 中；同理，活动7 [5,9] 的开始时间是 5，此时活动4 在时间 5 时结束，因此活动7 可以放到场地 4 中；同理，活动8 可以放到场地 1 中；活动9 可以放到场地 2 中；活动10 可以放到场地 5 中；活动11 可以放到场地 1 中。因此 5 个场地即可放置这 11 个活动，最小场地数为 5。因此整题选 ACDB。