第1讲算法引论优秀PPT.ppt

第一章第一章第一章第一章 算法引论算法引论算法引论算法引论例子例子:给定两个正整数给定两个正整数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)的最大公因子第一章第一章第一章第一章 算法引论算法引论算法引论算法引论什么是算法？什么是算法？它是一组它是一组有穷规则有穷规则的集合，它规定了解决某一的集合，它规定了解决某一 特定类特定类型问题的一系列运算。型问题的一系列运算。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、有穷性、有穷性:一个算法总是在有限步之后结束，且每一步一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成都可在有穷时间内完成.算法与程序的区分：算法与程序的区分：程序：与某种语言有关，能干脆在机器上运行。程序：与某种语言有关，能干脆在机器上运行。算法：与特定的语言无关，可用任何语言实现算法：与特定的语言无关，可用任何语言实现 ，甚至，甚至可以用自然语言实现，但是一般为了避开二义性，本书可以用自然语言实现，但是一般为了避开二义性，本书接受类接受类C C语言描述。语言描述。第一章第一章第一章第一章 算法引论算法引论算法引论算法引论 一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。是一个计算过程。是一个计算过程。是一个计算过程。有穷性与有效性的关系有穷性与有效性的关系：三、评价算法的标准三、评价算法的标准 有穷性是对算法的基本要求，假如一个算法要能运用，必需具有有效性。有效性是指算法在有效的时间里终止。时间困难性和空间困难性时间困难性和空间困难性第一章第一章第一章第一章 算法引论算法引论算法引论算法引论四、本书介绍的内容四、本书介绍的内容 1、如何设计算法：、如何设计算法：2、如何表示算法：类、如何表示算法：类C语言语言(自学自学page 2-5)3、如何确定（或称证明）算法：、如何确定（或称证明）算法：4、如何分析算法：、如何分析算法：5、如何测试算法：作时空分布图、如何测试算法：作时空分布图第一章第一章第一章第一章 算法引论算法引论算法引论算法引论1.2 1.2 算法设计的步骤算法设计的步骤一、问题的描述一、问题的描述例例:货郎担问题货郎担问题 设售货员在一天内要到设售货员在一天内要到5 5个城市去推销货物，已知从一个个城市去推销货物，已知从一个城市到其他城市的费用，求总费用最少的路途。给出的城市到其他城市的费用，求总费用最少的路途。给出的信息主要有五个城市的关系图及相应的费用矩阵。信息主要有五个城市的关系图及相应的费用矩阵。二、模型的拟制二、模型的拟制 建模阶段至少要考虑以下两个基本问题：建模阶段至少要考虑以下两个基本问题：1 1）最适合于这个问题的数学结构是什么？）最适合于这个问题的数学结构是什么？2 2）有没有已经解决了的类似问题可供借鉴？）有没有已经解决了的类似问题可供借鉴？第一章第一章第一章第一章 算法引论算法引论算法引论算法引论 在模型建立好了以后，应当依据所选定的模型对在模型建立好了以后，应当依据所选定的模型对问题重新陈述问题重新陈述,并考虑下列问题并考虑下列问题:(1)(1)模型是否清晰地表达了与问题有关的全部重要模型是否清晰地表达了与问题有关的全部重要的信息的信息?(2)(2)模型中是否存在与要求的结果相关的数学量模型中是否存在与要求的结果相关的数学量?(3)(3)模型是否正确反映了输入、输出的关系模型是否正确反映了输入、输出的关系?(4)(4)对这个模型处理起来困难吗？对这个模型处理起来困难吗？第一章第一章第一章第一章 算法引论算法引论算法引论算法引论152434724335211 对于货郎担问题，其数学模型是带权图，与此图相关的对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。是费用矩阵。第一章第一章第一章第一章 算法引论算法引论算法引论算法引论以货郎担问题为例：接受枚举法。以货郎担问题为例：接受枚举法。分析：分析：三、算法的具体设计三、算法的具体设计 算法的具体设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种操作来实现。输入：城市数目输入：城市数目n;n;费用矩阵费用矩阵C=(cij)n*nC=(cij)n*n输出：旅行路途输出：旅行路途TOUR;TOUR;最小费用最小费用MINMIN第一章第一章第一章第一章 算法引论算法引论算法引论算法引论Salesman(n)i 1;tour0;min while i=(n-1)!do pPHRMUTI(n-1,i);/PHRMUTI(n-1,i)是生成是生成1到到n-1的第的第i个排列的子过程个排列的子过程 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|大的大的任意一个常数，此定理都成立。任意一个常数，此定理都成立。定理定理1.1 1.1 若若A(n)=aA(n)=am mn nm m+a+a1 1n+an+a0 0是一个是一个m m次多项式，则次多项式，则A(n)=OA(n)=O(n(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 的的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和和nlognnlogn次运算次运算。第一章第一章第一章第一章 算法引论算法引论算法引论算法引论定义定义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)。一个算法的一个算法的一个算法的一个算法的f(n)=(g(n)f(n)=(g(n)f(n)=(g(n)f(n)=(g(n)意味着该算法在最好和最坏情意味着该算法在最好和最坏情意味着该算法在最好和最坏情意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。第一章第一章第一章第一章 算法引论算法引论算法引论算法引论五、算法分类（按时间）五、算法分类（按时间）多项式时间算法：凡可用多项式时间算法：凡可用多项式多项式来对其计算时间界限的算法。来对其计算时间界限的算法。指数时间算法：计算时间用指数时间算法：计算时间用指数函数指数函数界限的算法。界限的算法。以下六种计算时间的多项式时间算法是最为常见的，其关以下六种计算时间的多项式时间算法是最为常见的，其关系为：系为：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 O O（nlogn)nlogn)nlogn)nlogn)困难度高的算法往往是很困难的。困难度高的算法往往是很困难的。困难度高的算法往往是很困难的。困难度高的算法往往是很困难的。六、最好、最坏和平均状况六、最好、最坏和平均状况以依次检索为例以依次检索为例