计算机算法概论

1、计算机算法概论 算法设计与分析课程介绍算法设计与分析课程介绍 2 2）分治法及递归算法分析）分治法及递归算法分析 2. 算法设计算法设计 4） 贪心法贪心法 5） 动态规划法动态规划法 课程内容课程内容 1. 1.算法概述算法概述 3 3）图的算法）图的算法 1 1）穷举法）穷举法 计算机算法概论 9）概率算法概率算法 10）近似算法近似算法 8） NPNP完全性完全性 6） 回溯法回溯法 7） 分支分支- -限界法限界法 计算机算法概论 学习要点学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联 系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C/

2、C+语言描述算法的方法。 第一讲第一讲 算法概述算法概述 计算机算法概论 20世纪50年代，西方著名的词典中还未 曾收录过算法(Algorithm)一词，据西方数 学史家考证， Algorithm取自于古代阿拉 伯学者的名著复原和化简的规则一书 的作者的署名中的al-Khwarizmi，而从作 品名字中的al-jabr派生出了Algebra(代数) 一词。 随着时间的推移， Algorithm这个词的 含义，已经完全不同于它原来的含义了。 一、什么是算法？一、什么是算法？ 计算机算法概论 一个算法是一个有穷规则的集合。这些规则规一个算法是一个有穷规则的集合。这些规则规 定了解决某一问题的一个运

3、算序列。同时，一个算定了解决某一问题的一个运算序列。同时，一个算 法应该具有五个特性：有穷性、可行性、确定性、法应该具有五个特性：有穷性、可行性、确定性、 输入、输出。输入、输出。 1. 有穷性：规则的有限性。或者说，求解问题的有穷性：规则的有限性。或者说，求解问题的 运算序列，必须在有限的计算步后停止。运算序列，必须在有限的计算步后停止。 2. 可行性：每一计算步都是基本的、可实现的。可行性：每一计算步都是基本的、可实现的。 3. 确定性：每一条规则都是明确、无二义的。确定性：每一条规则都是明确、无二义的。 算法定义：算法定义： 计算机算法概论 5. 输出（输出（ 1）：算法产生与输入相关的

4、量。）：算法产生与输入相关的量。 4. 输入（输入（ 0）：算法开始执行之前指定初始值。：算法开始执行之前指定初始值。 二、算法的又一描述方式二、算法的又一描述方式 设：四元组（设：四元组（Q, I, , f ). 其中：其中：Q:状态集合状态集合； I, ：Q的子集，分别代表输入和输出的子集，分别代表输入和输出 f: 定义在定义在Q之上的一个映射之上的一个映射。 且有：若且有：若q ，则：，则：f(q) = q。 计算机算法概论 1. 描述计算序列描述计算序列： 若对于若对于I 的每一个输入的每一个输入x,由由f 定义一个计算序列：定义一个计算序列： y0 , y1 , y2 , 。 其中：

5、其中：y0 = x; yk+1 = f( yk ) (k 0)。 若一个计算序列在第若一个计算序列在第k步终止，且步终止，且k是使是使yK 的最小整数，则称的最小整数，则称yk是由是由x产生的输出。产生的输出。 2. 描述算法：描述算法： 一个算法是对于一个算法是对于I 中所有输入中所有输入x, 都能在有穷步都能在有穷步 内终止的一个计算序列。内终止的一个计算序列。 计算机算法概论 f0 y1 Q f1y2 x I yk fk-1 计算机算法概论 三、程序三、程序(Program) 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(1)。 例如操作系统，是一个在无限循环中执行

6、的程序，因 而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问 题由操作系统中的一个子程序通过特定的算法来实现。 该子程序得到输出结果后便终止。 计算机算法概论 四、算法复杂性分析四、算法复杂性分析 算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。 计算机算法概论 算法的时间复杂性算法的时间复杂性 （1）最坏情况最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n （2）最好情况最好情况下的时间复杂性 Tmin(n) = min T(I) | size(I)=n （3）

7、平均情况平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实 例I出现的 概率。 nIsize ITIp )( )()( 计算机算法概论 假设某算法的计算时间是f(n)，其中变量n 可以是输入或输出量，也可以是两者之和，还 可以是它们之一的某种测度(例如，数组的维数， 图的边数等)。g(n)是在事前分析中确定的某个 形式很简单的函数，它是独立于机器和语言的 函数，而f(n)则与机器和语言有关。 定义定义1.1 如果存在两个正常数c和n0,对于所有的n n0，有 |f(n)|c|g(n)| 记作f(n)=O(g(n) 算法时间的渐近表示算法时间的渐近表示 计算机

8、算法概论 当说一个算法具有当说一个算法具有O(g(n)的计算时间时，的计算时间时， 指的是如果此算法用指的是如果此算法用n值不变的同一类数值不变的同一类数 据在某台机器上运行时，所用的时间总据在某台机器上运行时，所用的时间总 是小于是小于|g(n)|的一个常数倍。所以的一个常数倍。所以g(n)是是 计算时间计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数的数 量级就是量级就是g(n)。当然，在确定。当然，在确定f(n)的数量的数量 级时总是试图求出最小的级时总是试图求出最小的g(n)，使得，使得 f(n)=O(g(n)。 计算机算法概论 证明：取证明：取n n0 0=1,=1,当当

9、n nn n0 0时，利用时，利用A(n)A(n)的定的定 义和一个简单的不等式，有义和一个简单的不等式，有 |A(n)| |a|A(n)| |am m|n|nm m +|a +|a1 1|n+|a|n+|a0 0| | (|a (|am m|+|a|+|am-1 m-1|/n+|a |/n+|a0 0|/n|/nm m)n)nm m (|a (|am m|+|a|+|a0 0|)n|)nm m 选取选取c= |ac= |am m|+|a|+|a0 0| |，定理立即得证。，定理立即得证。 定理定理1.1 1.1 若若A(n)=aA(n)=am mn nm m+a+a1 1n+an+a0 0

10、是一个是一个m m次多次多 项式，则项式，则A(n)=O(nA(n)=O(nm m) )。 计算机算法概论 这个定理表明，变量这个定理表明，变量n的固定阶数为的固定阶数为m的任一的任一 多项式，与此多项式的最高阶多项式，与此多项式的最高阶nm同阶。因此同阶。因此 计算时间为计算时间为m阶的多项式的算法，其时间都可阶的多项式的算法，其时间都可 用用O(nm)来表示。来表示。 事实上，只要将事实上，只要将n0取得足够大，可以证明只要取得足够大，可以证明只要 c是比是比|am|大的任意一个常数，此定理都成立。大的任意一个常数，此定理都成立。 计算机算法概论 从计算时间上可以把算法分成两类，从计算时间

11、上可以把算法分成两类， 凡可用凡可用 多项式来对其计算时间限界的算法，称为多多项式来对其计算时间限界的算法，称为多 项式时间算法项式时间算法(polynomial time algorithm)(polynomial time algorithm)； 而计算时间用指数函数限界的算法称为指数而计算时间用指数函数限界的算法称为指数 时间算法时间算法(exponential time algorithm)(exponential time algorithm)。 计算机算法概论 指数时间算法一般有以下几种，它们关系为：指数时间算法一般有以下几种，它们关系为： O(2n) O(n!) O(nn) 以下

12、六种计算时间的多项式时间算法是最为常见以下六种计算时间的多项式时间算法是最为常见 的，其关系为：的，其关系为： O(1)O(1)O(longn) O(longn) O(n) O(n) O(nlongn) O(nlongn) O(nO(n2 2) ) O(nO(n3 3) ) 因此，只要有人能将现在指数时间算法中因此，只要有人能将现在指数时间算法中 的任何一个算法化简为多项式时间算法，的任何一个算法化简为多项式时间算法， 那就取得了一个伟大的成就那就取得了一个伟大的成就! ! 计算机算法概论 算法分析中常见的复杂性函数算法分析中常见的复杂性函数 计算机算法概论 算法分析的基本法则算法分析的基本法

13、则 非递归算法：非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环 循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。 计算机算法概论 问题求解问题求解(Problem Solving) 证明正确性 分析算法 设计程序 理解问题 精确解或近似解 选择数据结构 算法设计策略 设计算法 计算机算法概论 五、算法设计的例子穷举法 例1.1 百鸡问题 公元5世纪末，数学家张丘建在算 经中，提出这样一个问题：“鸡翁一， 值钱五；鸡母一，值钱一；鸡雏三，值 钱一。百钱

14、买百鸡，问鸡翁、母、雏各 几何”。 计算机算法概论 l令a为公鸡只数，b为母鸡只数，c为小鸡只数 l a+b+c=100 (1) l5a+3b+c/3=100 (2) lc%3=0 (3) l上述百鸡问题中，a、b、c的可能取值范围为 0-100，对在此范围内的a、b、c的所有组合进 行测试，凡是满足上述3个约束方程的组合， 都是问题的解。 计算机算法概论 输入：所购买的3种鸡的总数目n 输出：满足问题的解的数目k，公鸡，母 鸡，小鸡的只数g，m，s 计算机算法概论 void chicken_question(int n,int k=0; for(a=0;a=n;a+) for(b=0;b=n

15、;b+) for(c=0;c=n;c+) if(a+b+c=n) mk=b; sk=c; k+; 计算机算法概论 当n=100时，内循环体执行次数大于100 万次 考虑到n元钱只可以买到n/5只公鸡，或 n/3只母鸡，有些组合可以不必考虑。而 小鸡的只数又与公鸡及母鸡的只数相关， 内循环可以省去。 这样，算法1.1中可以改为： 计算机算法概论 void chicken_problem(int n,int 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) mk=b; sk=c; k+ 计算机

16、算法概论 例1.2 货郎担问题 l某售货员要到若干个城市销售货物，已知各 城市之间的距离，要求售货员选择出发的城 市及旅行路线，使每一个城市仅经过一次， 最后回到原出发城市，而总路程最短。 l如果对任意数目的n个城市，分别用1-n的数 字编号，这个问题归结为带权有向图中，寻 找一条路径最短 的哈密尔顿回路问题。 l思考：存储的实现方法 计算机算法概论 l售货员的每一条路线，对应于城市编号 1,2, n的一个排列。用一个数组来存放 这个排列中的数据，数组中的元素依次 存放旅行路线中的城市编号。 ln个城市具有n!个排列，售货员共有n!条 路线可供选择。采用穷举法逐一计算每 一条路线的费用，从中找出费用最小的 路线，便可求出问