第1讲算法引论课件.ppt

1、例子例子:给定两个正整数给定两个正整数a a和和b,b,求它们的最大公因子求它们的最大公因子算法算法:欧几里德算法欧几里德算法输入输入:正整数正整数a a、b b输出：输出：a a和和b b的最大公因子的最大公因子第一章第一章 算法引论算法引论1.1 1.1 算法的基本概念算法的基本概念一、什么是算法及其与程序的区别一、什么是算法及其与程序的区别求解的数学模型为：gcd(a,b)=gcd(b,a)/gcd为求(a,b)的最大公因子的函数，其中abgcd(a,b)=gcd(b,a%b)/%为取模运算，求a除b的余数 =gcd(b,0)/当a%b=0时，b为(a,b)的最大公因子什么是算法？什么是

2、算法？它是一组它是一组有穷规则有穷规则的集合，它规定了解决某一的集合，它规定了解决某一 特定特定类型问题的一系列运算。类型问题的一系列运算。Gcd(int a,int b)/a,bN+1 if a b2 then swap(a,b);/交换a和b，保证a比b大3 n a%b;/a和b取余4 while n05 do a b;6 b n;7 n a%b;8 return b;二、算法的特征二、算法的特征 1 1、确定性、确定性 2 2、能行性、能行性 3 3、输入、输入 4 4、输出、输出 5 5、有穷性、有穷性:一个算法总是在有限步之后结束，且每一步一个算法总是在有限步之后结束，且每一步都可在

3、有穷时间内完成都可在有穷时间内完成.算法与程序的区别：算法与程序的区别：程序：与某种语言有关，能直接在机器上运行。程序：与某种语言有关，能直接在机器上运行。算法：与特定的语言无关，可用任何语言实现算法：与特定的语言无关，可用任何语言实现 ，甚至，甚至可以用自然语言实现，但是一般为了避免二义性，本书可以用自然语言实现，但是一般为了避免二义性，本书采用类采用类C C语言描述。语言描述。有穷性与有效性的关系有穷性与有效性的关系：三、评价算法的标准三、评价算法的标准 有穷性是对算法的基本要求，如果一个算法要能使用，有穷性是对算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在有效的时

4、间里终止。必须具有有效性。有效性是指算法在有效的时间里终止。时间复杂性和空间复杂性时间复杂性和空间复杂性四、本书介绍的内容四、本书介绍的内容 1、如何设计算法：、如何设计算法：2、如何表示算法：类、如何表示算法：类C语言语言(自学自学page 2-5)3、如何确定（或称证明）算法：、如何确定（或称证明）算法：4、如何分析算法：、如何分析算法：5、如何测试算法：作时空分布图、如何测试算法：作时空分布图1.2 1.2 算法设计的步骤算法设计的步骤一、问题的描述一、问题的描述例例:货郎担问题货郎担问题 设售货员在一天内要到设售货员在一天内要到5 5个城市去推销货物，已知从一个城市去推销货物，已知从一

5、个城市到其他城市的费用，求总费用最少的路线。给出个城市到其他城市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。的信息主要有五个城市的关系图及相应的费用矩阵。二、模型的拟制二、模型的拟制 建模阶段至少要考虑以下两个基本问题：建模阶段至少要考虑以下两个基本问题：1 1）最适合于这个问题的数学结构是什么？）最适合于这个问题的数学结构是什么？2 2）有没有已经解决了的类似问题可供借鉴？）有没有已经解决了的类似问题可供借鉴？在模型建立好了以后，应该依据所选定的模型对在模型建立好了以后，应该依据所选定的模型对问题重新陈述问题重新陈述,并考虑下列问题并考虑下列问题:(1)(1

6、)模型是否清楚地表达了与问题有关的所有重要模型是否清楚地表达了与问题有关的所有重要的信息的信息?(2)(2)模型中是否存在与要求的结果相关的数学量模型中是否存在与要求的结果相关的数学量?(3)(3)模型是否正确反映了输入、输出的关系模型是否正确反映了输入、输出的关系?(4)(4)对这个模型处理起来困难吗？对这个模型处理起来困难吗？32353147214234415721152434724335211 对于货郎担问题，其数学模型是带权图，与此图相关的对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。是费用矩阵。以货郎担问题为例：采用枚举法。以货郎担问题为例：采用枚举法。分析：分析：三、

7、算法的详细设计三、算法的详细设计 算法的详细设计是指设计求解某个具体问题的一算法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种操系列步骤，并且这些步骤可以通过计算机的各种操作来实现。作来实现。输入：城市数目输入：城市数目n;n;费用矩阵费用矩阵C=(cC=(cijij)n n*n n输出：旅行路线输出：旅行路线TOUR;TOUR;最小费用最小费用MINMINSalesman(n)i 1;tour0;min while i=(n-1)!do pPHRMUTI(n-1,i);/PHRMUTI(n-1,i)是生成是生成1到到n-1的第的第i个排列的子过程个排列的子过

8、程 cost(T(p)EFP(c,T(p)；/EFP(c,T)是由费用矩阵是由费用矩阵c及路线及路线T(p)所算得的总费用所算得的总费用 if cost(T(p)=nn=n0 0时，利用时，利用A(n)A(n)的定义和的定义和 一个简单的一个简单的不等式，有不等式，有取取c=|ac=|am m|+|+.+|a.+|a0 0|定理得证定理得证.事实上，只要将事实上，只要将n n0 0取得足够大，可以证明只要取得足够大，可以证明只要c c是比是比|a|am m|大大的任意一个常数，此定理都成立。的任意一个常数，此定理都成立。10100|()|(|/|/)(|)mmmmmmmmA nananaaan

9、annaan定理定理1.1 1.1 若若A(n)=aA(n)=am mn nm m+a+a1 1n+an+a0 0是一个是一个m m次多项式，则次多项式，则A(n)=O(nA(n)=O(nm m)。此定理表明，此定理表明，变量变量n n的固定阶数为的固定阶数为m m的任一多项式，的任一多项式，与此多项式的最高阶与此多项式的最高阶n nm同阶，同阶，因此计算时间为因此计算时间为m m阶的多项阶的多项式的算法，其时间都可用式的算法，其时间都可用O(nO(nm).).例如，若一个算法有数例如，若一个算法有数量级为量级为c c1 1n nm1m1,c,c2 2n nm2m2,c ck kn nmkmk

10、 的的k k个语句，则此算法的数个语句，则此算法的数量级就是量级就是 c c1 1n nm1m1+c+c2 2n nm2m2+c+ck kn nmkmk 由定理由定理1.11.1，它等于，它等于O(nO(nm m),),其中其中m=maxmm=maxmi i|1|1i k n2nlognn=1024104857610240时间（n=1024)1.05s0.01sn=2048419430422528时间（n=2048)4.2s0.02s例子：假设有解决同一个问题的两个算法，它们有例子：假设有解决同一个问题的两个算法，它们有n n个输个输 入，分别要求入，分别要求n n2 2和和nlognnlog

11、n次运算次运算。定义定义1.3 1.3 如果存在两个正常数如果存在两个正常数c c和和n n0 0,对于所有对于所有n nn n0 0,有有|f(n)|c|g(n)|f(n)|c|g(n)|则记为则记为f(n)=(g(n)f(n)=(g(n)。定义定义1.4 1.4 如果存在两个正常数如果存在两个正常数c1,c2,c1,c2,和和n n0 0,对于所有的对于所有的n n n n0 0,有有 则记为则记为f(n)=(g(n)f(n)=(g(n)。12()|()|()|cg nfncg n五、算法分类（按时间）五、算法分类（按时间）多项式时间算法：凡可用多项式时间算法：凡可用多项式多项式来对其计算

12、时间界限的算法。来对其计算时间界限的算法。指数时间算法：计算时间用指数时间算法：计算时间用指数函数指数函数界限的算法。界限的算法。以下六种计算时间的多项式时间算法是最为常见的，其关以下六种计算时间的多项式时间算法是最为常见的，其关系为：系为：O(1)O(logn)O(n)O(nlogn)O(nO(1)O(logn)O(n)O(nlogn)O(n2 2)O(n)O(n3 3)指数时间算法一般有指数时间算法一般有O(2O(2n n)、O(n!)O(n!)和和O(nO(nn n)等。其关系为等。其关系为 O(2O(2n n)O(n!)O(n)O(n!)O(nn n)当数据集的规模很大时，要在现代计算机上运当数据集的规模很大时，要在现代计算机上运行具有比行具有比O O（nlogn)nlogn)复杂度高的算法往往是很困难的。复杂度高的算法往往是很困难的。六、最好、最坏和平均情况六、最好、最坏和平均情况以顺序检索为例以顺序检索为例