计算机算法概论

计算机算法概论第一页，共三十五页，编辑于2023年，星期五

9）概率算法

10）近似算法

8）NP—完全性

6）回溯法

7）分支-限界法

第二页，共三十五页，编辑于2023年，星期五学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C/C++语言描述算法的方法。第一讲算法概述第三页，共三十五页，编辑于2023年，星期五

20世纪50年代，西方著名的词典中还未曾收录过算法(Algorithm)一词，据西方数学史家考证，Algorithm取自于古代阿拉伯学者的名著《复原和化简的规则》一书的作者的署名中的al-Khwarizmi，而从作品名字中的al-jabr派生出了Algebra(代数)一词。 随着时间的推移，Algorithm这个词的含义，已经完全不同于它原来的含义了。一、什么是算法？

第四页，共三十五页，编辑于2023年，星期五

一个算法是一个有穷规则的集合。这些规则规定了解决某一问题的一个运算序列。同时，一个算法应该具有五个特性：有穷性、可行性、确定性、输入、输出。

1.有穷性：规则的有限性。或者说，求解问题的运算序列，必须在有限的计算步后停止。

2.可行性：每一计算步都是基本的、可实现的。

3.确定性：每一条规则都是明确、无二义的。算法定义：

第五页，共三十五页，编辑于2023年，星期五

5.输出（1）：算法产生与输入相关的量。

4.输入（0）：算法开始执行之前指定初始值。二、算法的又一描述方式

设：四元组（Q,I,,f).

其中：Q:状态集合；

I,：Q的子集，分别代表输入和输出

f:定义在Q之上的一个映射。

且有：若q，则：f(q)=q。

第六页，共三十五页，编辑于2023年，星期五

1.描述计算序列：

若对于I的每一个输入x,由f

定义一个计算序列：y0,y1,y2,。其中：y0=x;yk+1=f(yk)(k0)。若一个计算序列在第k步终止，且k是使yK

的最小整数，则称yk是由x产生的输出。

2.描述算法：一个算法是对于I中所有输入x,都能在有穷步内终止的一个计算序列。第七页，共三十五页，编辑于2023年，星期五f0y1Qf1y2

xIykfk-1第八页，共三十五页，编辑于2023年，星期五三、程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(1)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。第九页，共三十五页，编辑于2023年，星期五四、算法复杂性分析

算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。第十页，共三十五页，编辑于2023年，星期五算法的时间复杂性（1）最坏情况下的时间复杂性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情况下的时间复杂性

Tmin(n)=min{T(I)|size(I)=n}（3）平均情况下的时间复杂性

Tavg(n)=

其中I是问题的规模为n的实例，p(I)是实例I出现的概率。第十一页，共三十五页，编辑于2023年，星期五 假设某算法的计算时间是f(n)，其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度(例如，数组的维数，图的边数等)。g(n)是在事前分析中确定的某个形式很简单的函数，它是独立于机器和语言的函数，而f(n)则与机器和语言有关。定义1.1

如果存在两个正常数c和n0,对于所有的n≥n0，有

|f(n)|≤c|g(n)|记作f(n)=O(g(n))算法时间的渐近表示第十二页，共三十五页，编辑于2023年，星期五当说一个算法具有O(g(n))的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。当然，在确定f(n)的数量级时总是试图求出最小的g(n)，使得f(n)=O(g(n))。第十三页，共三十五页，编辑于2023年，星期五证明：取n0=1,当n≥n0时，利用A(n)的定义和一个简单的不等式，有|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm

≤(|am|+…+|a0|)nm选取c=|am|+…+|a0|，定理立即得证。定理1.1

若A(n)=amnm+…+a1n+a0

是一个m次多项式，则A(n)=O(nm)。第十四页，共三十五页，编辑于2023年，星期五这个定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶。因此计算时间为m阶的多项式的算法，其时间都可用O(nm)来表示。事实上，只要将n0取得足够大，可以证明只要c是比|am|大的任意一个常数，此定理都成立。第十五页，共三十五页，编辑于2023年，星期五从计算时间上可以把算法分成两类，凡可用多项式来对其计算时间限界的算法，称为多项式时间算法(polynomialtimealgorithm)；而计算时间用指数函数限界的算法称为指数时间算法(exponentialtimealgorithm)。第十六页，共三十五页，编辑于2023年，星期五指数时间算法一般有以下几种，它们关系为：O(2n)＜O(n!)＜O(nn)以下六种计算时间的多项式时间算法是最为常见的，其关系为：O(1)＜O(longn)＜O(n)＜O(nlongn)＜O(n2)＜O(n3)因此，只要有人能将现在指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就!第十七页，共三十五页，编辑于2023年，星期五算法分析中常见的复杂性函数第十八页，共三十五页，编辑于2023年，星期五算法分析的基本法则非递归算法：（1）for/while循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。第十九页，共三十五页，编辑于2023年，星期五问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法第二十页，共三十五页，编辑于2023年，星期五五、算法设计的例子—穷举法例1.1百鸡问题 公元5世纪末，数学家张丘建在《算经》中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱一；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何”。

第二十一页，共三十五页，编辑于2023年，星期五令a为公鸡只数，b为母鸡只数，c为小鸡只数

a+b+c=100(1)5a+3b+c/3=100(2)c%3=0(3)上述百鸡问题中，a、b、c的可能取值范围为0-100，对在此范围内的a、b、c的所有组合进行测试，凡是满足上述3个约束方程的组合，都是问题的解。第二十二页，共三十五页，编辑于2023年，星期五输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k，公鸡，母鸡，小鸡的只数g[]，m[]，s[]第二十三页，共三十五页，编辑于2023年，星期五voidchicken_question(intn,int&k,intg[],intm[],ints[]){ inta,b,c; k=0; for(a=0;a<=n;a++){ for(b=0;b<=n;b++){ for(c=0;c<=n;c++){ if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){ g[k]=a; m[k]=b; s[k]=c; k++; } } } }}第二十四页，共三十五页，编辑于2023年，星期五当n=100时，内循环体执行次数大于100万次考虑到n元钱只可以买到n/5只公鸡，或n/3只母鸡，有些组合可以不必考虑。而小鸡的只数又与公鸡及母鸡的只数相关，内循环可以省去。这样，算法1.1中可以改为：第二十五页，共三十五页，编辑于2023年，星期五voidchicken_problem(intn,int&k,intg[],intm[],ints[]){ inti,j,a,b,c; k=0; i=n/5; j=n/3; for(a=0;a<=i;a++){ for(b=0;b<=j;b++){ c=n-a-b; if((5*a+3*b+c/3==n)&&(c%3==0)){ g[k]=a; m[k]=b; s[k]=c; k++ } } }}第二十六页，共三十五页，编辑于2023年，星期五例1.2货郎担问题某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最短。如果对任意数目的n个城市，分别用1-n的数字编号，这个问题归结为带权有向图中，寻找一条路径最短的哈密尔顿回路问题。思考：存储的实现方法第二十七页，共三十五页，编辑于2023年，星期五售货员的每一条路线，对应于城市编号1,2,…,n的一个排列。用一个数组来存放这个排列中的数据，数组中的元素依次存放旅行路线中的城市编号。n个城市具有n!个排列，售货员共有n!条路线可供选择。采用穷举法逐一计算每一条路线的费用，从中找出费用最小的路线，便可求出问题的解。算法1.3穷举法版本的货郎担问题输入：城市个数n，费用矩阵c[][]输出：旅行路线t[]，最小费用min第二十八页，共三十五页，编辑于2023年，星期五voidsalesman_problem(intn,float&min,intt[],floatc[][]){ intp[n],i=1; floatcost; min=MAx_FLoat_NUM; while(i<=n!){

产生n个城市的第i个排列于p; cost=路线p的费用；

if(cost<min){

把数组p的内容复制到数组t；

min=cost; } i++; }}第二十九页，共三十五页，编辑于2023年，星期五六、若干问题

(1)Euler回路：给定有向图G。判定：G中是否存在经过每一条边恰好一次的回路？

(2)Hamilton回路：给定有向图G。判定：G中是否存在经过每一条顶点恰好一次的回路？

(3)旅行商问题：给定整数n2,nn距离矩阵dij

，以及整数B0。判定：是否存在{1,2,…,n}的一个排列，使得C()B。第三十页，共三十五页，编辑于2023年，星期五

(4)独立集问题：给定无向图G和整数k2。判定：图G是否存在顶点集V的子集C满足|C|

K,并使得对所有vi，vjC,在vi和vj之间没有边。

(5)Clique问题：给定无向图G和整数k2。判定：图G是否存在顶点集V的子集C满足|C|

K,并使得对所有vi，vjC,在vi和vj之间有边。

(6)顶点覆盖问题：给定无向图G和整数B2。判定：图G是否存在顶点集V的子集C满足|C|

B,使得C覆盖G的所有边。（“覆盖”：若一个顶点集V至少包含某条边的一个端点，则称顶点集V覆盖边e。）第三十一页，共三十五页，编辑于2023年，星期五(7)整数划分问题：给定用二进制表示的n个非负整数a1,a2,…,an的集合。判定：是否存在子集P{1,2,…,n},使得iP

ai=iPai？(8)一进制整数划分问题：给定用一进制表示的n个非负整数a1,a2,…,an的集合。判定：是否存在子集P{1,2,…,n},使得iP

ai=iPai？

(9)布尔可满足性问题：

文字：x1x1x2x3x3x4

子句：(x1x2)(x1x2x4)(x1x3)合取范式形式的布尔公式：

F=(x1x2)(x1x2x4)(x1x3)第三十二页，共三十五页，编辑于2023年，星期五

若存在对变元的一组赋值，使得F取真值，则称F为可满足的。

(10)二元可满足性问题：二元合取范式形式的布尔公式:所有子句最多有两个文字的合取范式形式的布尔公式。第三十三页，共三十五页，编辑于2023年，星期五

(11)0/1背包问题