第1讲算法引论课件.ppt

《第1讲算法引论课件.ppt》由会员分享，可在线阅读，更多相关《第1讲算法引论课件.ppt（25页珍藏版）》请在三一办公上搜索。

1、例子:给定两个正整数a和b,求它们的最大公因子算法:欧几里德算法输入:正整数a、b输出：a和b的最大公因子,第一章 算法引论,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);/交换

2、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、确定性 2、能行性 3、输入 4、输出 5、有穷性:一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成.,算法与程序的区别：程序：与某种语言有关，能直接在机器上运行。算法：与特定的语言无关，可用任何语言实现，甚至可以用自然语言实现，但是一般为了避免二义性，本书采用类C语言描述。,一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。,有穷性与有效性的关系：,三、评价算法的标准,有穷性是对算法的基本要求，如果一个算法要能使

3、用，必须具有有效性。有效性是指算法在有效的时间里终止。,时间复杂性和空间复杂性,四、本书介绍的内容,1、如何设计算法：2、如何表示算法：类C语言(自学page 2-5)3、如何确定（或称证明）算法：4、如何分析算法：5、如何测试算法：作时空分布图,1.2 算法设计的步骤,一、问题的描述,例:货郎担问题 设售货员在一天内要到5个城市去推销货物，已知从一个城市到其他城市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。,二、模型的拟制 建模阶段至少要考虑以下两个基本问题：1）最适合于这个问题的数学结构是什么？2）有没有已经解决了的类似问题可供借鉴？,在模型建立好了以后，

4、应该依据所选定的模型对问题重新陈述,并考虑下列问题:,(1)模型是否清楚地表达了与问题有关的所有重要的信息?(2)模型中是否存在与要求的结果相关的数学量?(3)模型是否正确反映了输入、输出的关系?(4)对这个模型处理起来困难吗？,对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。,以货郎担问题为例：采用枚举法。分析：,三、算法的详细设计,算法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种操作来实现。,输入：城市数目n;费用矩阵C=(cij)n*n输出：旅行路线TOUR;最小费用MIN,Salesman(n)i 1;tour0;min while i=

5、(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)min tourT(p);mincost(T(p)ii+1;print min,tour,四、算法的正确性 可以分两步考虑:(1)算法的终止性；(2)算法的每一步是否都正确 算法的正确性并不蕴涵算法的有效性。,五、算法分析 时间复杂性和空间复杂性 以上货郎担问题的时间复杂性是：O(n!),六、文档的编制,（1）注释（2）算法的流程图（3）对输入/输出的要

6、求（4）正确性证明（5）时间复杂性和空间复杂性的分析,二、算法分析的要点 1、确定使用的运算和执行这些运算所用的时间。运算分为两类(1)基本运算；(2)“组合”运算由基本运算组成。,1.3 算法分析,一、算法分析的原因 1、为了对算法的某些特定的输入，估计或限界该算法所需要的空间和运行时间。2、为了建立衡量算法的优劣的标准，用以比较同一问题的不同算法。,时间是固定量,时间是变化量,2、确定能反映出算法在各种情况下工作的数据集构造出能产生最好、最坏和有代表性情况的数据配置。,三、算法分析的两个阶段,1、事前分析求出该算法的一个时间限界函数。,2、事后测试收集此算法的执行时间和实际占用空间的统计资

7、料。,就算法分析而言，一条语句的数量级指的是执行它的频率，而一个算法的数量级则指的是它所有语句执行频率的和。确定一个算法的数量级是十分重要的，它在本质上反映了一个算法所需要的计算时间。,四、计算时间的渐进表示 假设某种算法的计算时间是g(n),其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度（例如，数组的维数，图的边数等等）。f(n)是在事前分析中确定的某个形式很简单的函数，例如，nm,logn,2n,n!等。它是独立于机器和语言的函数，而g(n)则与机器和语言有关。,定义1.1 如果存在两个正常数c和n0，对于所有的nn0，|g(n)|c|f(n)|则记作g(n)=

8、(f(n).因此，当说一个算法具有O(f(n)的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|f(n)|的一个常数倍。所以f(n)是计算时间g(n)的一个上界函数，g(n)的数量级就是f(n)。,定义1.2：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作:T(n)O(f(n)随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。,证明：取n0=1,当n=n0时，利用A(n)的定义和 一个简单的不等式，有取c=|am|+.+|a0|定理得证.事实上，只要将n0取得足够

9、大，可以证明只要c是比|am|大的任意一个常数，此定理都成立。,定理1.1 若A(n)=amnm+a1n+a0是一个m次多项式，则A(n)=O(nm)。,此定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶，因此计算时间为m阶的多项式的算法，其时间都可用O(nm).例如，若一个算法有数量级为c1nm1,c2nm2,cknmk 的k个语句，则此算法的数量级就是 c1nm1+c2nm2+cknmk 由定理1.1，它等于O(nm),其中m=maxmi|1i k,例子：假设有解决同一个问题的两个算法，它们有n个输 入，分别要求n2和nlogn次运算。,定义1.3 如果存在两个正常数

10、c和n0,对于所有n n0,有|f(n)|c|g(n)|则记为f(n)=(g(n)。定义1.4 如果存在两个正常数c1,c2,和n0,对于所有的n n0,有 则记为f(n)=(g(n)。一个算法的f(n)=(g(n)意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。,五、算法分类（按时间）多项式时间算法：凡可用多项式来对其计算时间界限的算法。指数时间算法：计算时间用指数函数界限的算法。,以下六种计算时间的多项式时间算法是最为常见的，其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法一般有O(2n)、O(n!)和O(nn)等。其关系为 O(2n)O(n!)O(nn),注意：当数据集的规模很大时，要在现代计算机上运行具有比O（nlogn)复杂度高的算法往往是很困难的。,六、最好、最坏和平均情况以顺序检索为例,