河北科技师范学院
欧美学院
算法设计与分析个人总结
指导教师
院 系
班 级
学生姓名
学 号
引言：对于计算机科学来说，算法分析与设计是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本书系统地阐述了算法设计的方法、技术和应用实例。
一、算法复杂性分析的方法介绍
1.1算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
关于算法的复杂性，有两个问题要弄清楚：
1. 用怎样的一个量来表达一个算法的复杂性；
2. 对于给定的一个算法，怎样具体计算它的复杂性。
比较两对算法的效率
考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A[1..m]（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得A=c；若找不到，则返回一个0。
问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足A=c；或者扫到A的最后一个分量，经检测仍不满足A=c。我们用一个函数Search来表达这个算法： Function Search (c:integer):integer;
Var J:integer;
Begin
J:=1; {初始化}
{在还没有到达A的最后一个分量且等于c的分量还没有找到时，
查找下一个分量并且进行检测}
While (A
j:=j+1;
If A[j]=c then search:=j {在数组A中找到等于c的分量，且此分量的下标为j}
else Search:=0; {在数组中找不到等于c的分量}
End;
容易看出，在最坏的情况下，这个算法要检测A的所有m个分量才能判断在A中找不到等于c的分量。
解决问题1的另一个算法利用到已知条件中A已排好序的性质。它首先拿A的中间分量A[m/2]与c比较，如果A[m/2]=c则解已找到。如果A[m/2]>c，则c只可能在A[1],A[2],..,A[m/2-1]之中，因而下一步只要在A[1], A[2], .. ，A[m/2-1]中继续查找；如果A[m/2]
下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得A=c，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于c的分量，后一种情况则找不到。
这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数B_Search来表达： Function B_Search ( c: integer):integer;
Var
L,U,I : integer; {U和L分别是要查找的数组的下标的上界和下界}
Found: boolean;
Begin
L:=1; U:=m; {初始化数组下标的上下界}
Found:=false; {当前要查找的范围是A[L]..A[U]。}
{当等于c的分量还没有找到且U>=L时，继续查找}
While (not Found) and (U>=L) do
Begin
I:=(U+L) div 2; {找数组的中间分量}
If c=A[I] then Found:=Ture
else if c>A[I] then L:=I+1
else U:=I-1;
End;
If Found then B_Search:=1
else B_Search:=0;
End;
容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中
算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。
以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。
上图是运行这两种算法的时间曲线。该图表明，当m适当大（m>m0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。
不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同。
一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。
1.2复杂性的计量 ：
算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入
和本身，用C表示算法的复杂性，那么应该有：
C =F(N,I,A)
其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂
性分开，并分别用T和S来表示，那么应该有：
T =T(N,I,A) (2.1)
和 S =S(N,I,A) (2.2)
通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为
T =T(N,I)
和 S =S(N,I)
二、常见的算法分析设计策略介绍
2.1递归与分治策略
2.1.1 递归算法：
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函
数称为递归函数。
递归算法的实质：
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法的特点：
递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法要求：
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
递归算法举例：
描述：把一个整数按n(2
参数说明：s: 保存转换后得到的结果。
n: 待转换的整数。
b: n进制（2
void
numbconv(char *s, int n, int b)
{
int len;
if(n == 0) {
strcpy(s, "");
return;
}
/* figure out first n-1 digits */
numbconv(s, n/b, b);
/* add last digit */
len = strlen(s);
s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
s[len+1] = '\0';
}
void
main(void)
{
char s[20];
int i, base;
FILE *fin, *fout;
fin = fopen("palsquare.in", "r");
fout = fopen("palsquare.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%d", &base);
/*PLS set START and END*/
for(i=START; i
numbconv(s, i*i, base);
fprintf(fout, "%s\n", s);
}
exit(0);
}
2．1.2分治法
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分
而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序
算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)
分治策略是：
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n
较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P) 1. if |P|≤n0 2. then return(ADHOC(P)) 3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。
2.1.3递归与分治
如果原问题可分割成k个子问题，1
2.2 动态规划
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
动态规划适用条件：
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2.无后向性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句
话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3.子问题的重叠性 动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。 动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
2.3 贪心算法
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在
当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的
许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解。
2.4 回溯法
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
用回溯法解题的一般步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
2.5分支界限法
分支限界法是最佳优先(包括广度优先在内)的搜索法，也是一种较为通用的算法。其搜索的控制是采用有序的队列，即每次优先搜索评价函数值最小的结点，从而希望较快地找到最佳的路径或排列。与其它算法相比，时间复杂性无本质区别。但好的评价函数可有小的常数，提高了效率。
分支限界法的求解目标与回溯法的目标
A 分支限界法与回溯法的求解目标不同。
B 回溯法的求解目标是找出解空间树T中满足约束条件的所有解。
C 分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
2.6贪心算法应用举例
用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值Vi/Wi，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超出C，则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进行下去，直到背包装 满为止。
像这种取选单位重量价值最高的择策略对0-1背包问题就不怎么适用。若有3种物品，背包的容量为50，三种物品的重量和价值分别为10 60，20 100，30 120。因此，物品1单位价值6，物品2单位价值5，物品3单位价值4。若依贪心选择策略，应首选物品1装入，再选物品2装入。可以很明显看出最优的是物品2，3而不是1，2。
C++源程序
////////////////////////////////////////////////
//该程序用贪心算法来求解0-1背包问题
//采用贪婪准则：每次选择p/w最大的物品放入背包。
////////////////////////////////////////////////
#include
#include
#include
#include "time.h"
#include "windows.h"
#include
#include
#define num 100
void bagloading(int x[],float p[],float w[],float c,int n)
{
//x[]取值为0或1，x[i]=1当且仅当背包i背装载；
//p[]是物品价值；
//w[]是物品重量；
//c表示背包的容量；
//n表示物品的件数；
float t,k,pw[num];
int i,j,m,kk;
for(i=0;i
pw[i]=p[i]/w[i];
//对各个点的坐标按由大到小进行排序(使用改进的冒泡排序)
m=n-1;
while (m>0)
{
kk=0;
for(j=0;j
if (pw[j]
{
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
k=w[j];
w[j]=w[j+1];
w[j+1]=k;
kk=j;
}
m=kk;
}
//按p/w次序从大到小选择物品
i=0;
while(i
{
c-=w[i];
i++;
}
}
int main()
{
int n,all;
float c,p1,w1;
float p[num];
float w[num];
int x[num];
int i;
cout
cin>>n;
cout
cin>>c;
cout
格隔开，回车后输入另一个物品："
//通过键盘依次输入各物品的价值与重量
for(i=0;i
{
cin>>p[i]>>w[i];
}
//调用函数
bagloading(x,p,w,c,n);
//统计物品的总价值、总重量以及件数并输出
//统计装入物品的价值及重量并输出
all=0;
p1=0.0;
w1=0.0;
for(i=0;i
if(x[i]==1)
{
all++;
p1=p1+p[i];
w1=w1+w[i];
}
cout
cout
cout
{
cout
for(i=0;i
if(x[i]==1)
cout
}
system("pause");
return 0;
}
2.7总结或对比分析
四种算法都各有其优缺点，判断用何种算法，取决于具体问题的具体分析，看是否适用本身，能达到最优算法。动态规划算法与分治算法相似。用于贪心算法的有活动安排问题，最优装载问题，哈夫曼编码问题，单源最短路径问题。对于回溯法，通过约束找到满足条件的所有解，特点为能进就进，不能进就退回来，与递归类似。分支法与回溯法类似，但解的目标是通过约束找到满足条件的一个解，或找到在某种意义下的最优解。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
三、学习体会及其影响
通过对《计算机算法设计与分析》的学习，让我的编程思路变得更开阔了，能编写出比原来跟优质的程序。也让我更加的知道怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。让我拥有了更严格的设计与分析算法的思维方式，别且改变了我随意拼凑算法的习惯。