《高中数学 第11章 算法初步 11_1 算法概念和例子课件 湘教版必修51》由会员分享，可在线阅读，更多相关《高中数学 第11章 算法初步 11_1 算法概念和例子课件 湘教版必修51（197页珍藏版）》请在金锄头文库上搜索。
1、例子:给定两个正整数m和n,求它们的最大公因子 算法:欧几里德算法 输入:正整数m、n 输出：m和n的最大公因子,11.1 算法概念和例子,一、什么是算法及其与程序的区别,S1:保证m=n,如果mn，则m、n的值互换，否则转S2. S2:求余数。令r=m mod n,（0=rn) S3:判断余数r是否为0。如果r是0，则算法终止，n为答案，否则转S4. S4:置换。即mn,nr,转S2.,什么是算法？,它是一组有穷规则的集合，它规定了解决某一特定类型问题的一系列运算。,二、算法的特征 1、确定性 2、能行性 3、输入 4、输出 5、有穷性:一个算法总是在有限步之后结束，且每一步都可在有穷时间内
2、完成.,算法与程序的区别： 程序：与某种语言有关，能直接在机器上运行。 算法：与特定的语言无关，可用任何语言实现 ，甚至可以用自然语言实现，但是一般为了避免二义性，本书采用类C语言描述。,一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。,有穷性与有效性的关系：,三、评价算法的标准,有穷性是对算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在规定的时间里终止。,时间复杂性和空间复杂性,1.2 算法设计的步骤,一、问题的描述,例:货郎担问题 设售货员在一天内要到5个城市去推销货物，已知从一个城市到其他城市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系
3、图及相应的费用矩阵。,二、模型的拟制 建模阶段至少要考虑以下两个基本问题： 1）最适合于这个问题的数学结构是什么？ 2）有没有已经解决了的类似问题可供借鉴？,在模型建立好了以后，应该依据所选定的模型对问题重新陈述,并考虑下列问题:,(1)模型是否清楚地表达了与问题有关的所有重要的信息? (2)模型中是否存在与要求的结果相关的数学量? (3)模型是否正确反映了输入、输出的关系? (4)对这个模型处理起来困难吗？,对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。,以货郎担问题为例：采用枚举法。 分析：,三、算法的详细设计,算法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤
4、可以通过计算机的各种操作来实现。,输入：城市数目n;费用矩阵C=(cij)n*n 输出：旅行路线TOUR;最小费用MIN,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)min tourT(p); mincost(T(p) ii+1; print min, tour,四、算法的正确性 可以分两步考虑: (1)算法的终止性；
5、 (2)算法的每一步是否都正确 算法的正确性并不蕴涵算法的有效性。,五、算法分析 时间复杂性和空间复杂性 以上货郎担问题的时间复杂性是：O(n!),六、文档的编制,（1）注释 （2）算法的流程图 （3）对输入/输出的要求 （4）正确性证明 （5）时间复杂性和空间复杂性的分析,二、算法分析的要点 1、确定使用的运算和执行这些运算所用的时间。 运算分为两类 (1)基本运算；(2)“组合”运算由基本运算组成。,1.3 算法分析,一、算法分析的原因 1、为了对算法的某些特定的输入，估计或限界该算法所需要的空间和运行时间。 2、为了建立衡量算法优劣的标准，用以比较同一问题的不同算法。,时间是固定量,时间
6、是变化量,2、确定能反映出算法在各种情况下工作的数据集构造出能产生最好、最坏和有代表性情况的数据配置。,三、算法分析的两个阶段,1、事前分析求出该算法的一个时间限界函数。,2、事后测试收集此算法的执行时间和实际占用空间的统计资料。,就算法分析而言，一条语句的数量级指的是执行它的频率，而一个算法的数量级则指的是它所有语句执行频率的和。 确定一个算法的数量级是十分重要的，它在本质上反映了一个算法所需要的计算时间。,四、计算时间的渐进表示 假设某种算法的计算时间是f(n),其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度（例如，数组的维数，图的边数等等）。g(n)是在事前分
7、析中确定的某个形式很简单的函数，例如，nm,logn,2n,n!等。它是独立于机器和语言的函数，而f(n)则与机器和语言有关。,定义1.2 如果存在两个正常数c和n0，对于所有的nn0， |f(n)|c|g(n)| 则记作f(n)=(g(n). 因此，当说一个算法具有O(g(n)的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。,定义1.1：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作:T(n)O(f(n) 随着问题规模
8、n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。,证明：取n0=1,当n=n0时，利用A(n)的定义和 一个简单的不等式，有 取c=|am|+.+|a0| 定理得证. 事实上，只要将n0取得足够大，可以证明只要c是比|am|大的任意一个常数，此定理都成立。,定理1.1 若A(n)=amnm+ a1n+ a0是一个m次多项式，则A(n)=O(nm)。,此定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶，因此计算时间为m阶的多项式的算法，其时间都可用O(nm).例如，若一个算法有数量级为c1nm1, c2nm2, cknmk 的
9、k个语句，则此算法的数量级就是 c1nm1 +c2nm2+cknmk 由定理1.1，它等于O(nm),其中m=maxmi|1i k,例子：假设有解决同一个问题的两个算法，它们有n个输 入，分别要求n2和nlogn次运算。,定义1.3 如果存在两个正常数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)意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。,五、算法分类（按时间） 多项式时间算法：凡可用
10、多项式来对其计算时间界限的算法。 指数时间算法：计算时间用指数函数界限的算法。,以下六种计算时间的多项式时间算法是最为常见的，其关系为： 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)复杂度高的算法往往是很困难的。,六、最好、最坏和平均情况 以顺序检索为例,第二章 分治法 2.1 方法概述,一、基本思想 1、设计思想：将整个问题分成若干个小问题后,分而治之。 2、适用条件： 问题规模很大；
11、可以分成若干个与原问题性质相同的子问题，并可以分别求解。 子问题的解通过整合可以得到原问题的解。 3、设计方法：使用递归策略。,4、 设计步骤 (1)分解：将原问题分解为若干个相互独立、与原问题形式相同的子问题； (2)求解：若子问题容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决； (3)合并：将已求解的各个子问题的解，逐步合并以得到原问题的解。,二、分治法的算法设计模式 Divide-and-Conquer(n) /n为问题规模 1 if n = n0 /n0 为可解子问题的规模 2 then 3 4 解子问题 5 return( 子问题的解 ) 6 4 for i 1 to
12、 k /分解为k个子问题 5 do yi Divide-and-Conquer(|Pi|)/递归解决Pi 6 T MERGE(y1,y2,.,yk) /合并子问题 7 return T,递归过程,注意：分治法可以用递归实现，也可以用循环实现。,其中：其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,.,Pk的相应的解y1,y2,.,yk合并为P的解。,时间复杂性分析：,其中，T(n)是输入规模为n的Divide-and-Conquer的时间
13、，g(n)是对足够小的输入规模能直接计算出答案的时间，f(n)是MERGE的时间。,倘若所分成的两个子问题的输入规模大致相等，则Divide-and-Conquer总的计算时间可以用下面的递推关系来表示： (n足够小) (否则),2.2 二 分 检 索,一、问题描述 已知一个按非降次序排列的元素表a1,a2,an,要求判定某给定元素x是否在该表中出现。若是，则找出x在表中的位置，并将此下标值赋给变量j；若非，则将j置成0。,对于I2，通过比较x和ak容易得到解决。如果x= ak,则j=k且不需再对I1和I3求解；否则，在I2 子问题的j=0，此时若xak,只有I3留待求解，在I1子问题中的j=
14、0。在ak作了比较之后，留待求解的问题（如果有的话）可以再一次使用分治法来求解。如果对所求解的问题（或子问题）所选的下标k都是其元素的中间元素下标（例如，对于I，k=(n+1)/2）,则所产生的算法就是通常所说的二分检索。,三、二分检索算法 算法2.3 二分检索 /给定一个按非降次序排列的元素数组A(1:n),n1,判 断x是否出现。若是，置j，使得x=A(j),若非，j=0/ BINSEARCH(A,n,x) 1 low 1 2 high n,3 while lowhigh，数组A中没有找到x，返回j0 4 do 5 6 /取处于low和high之间的中间值 7 if x=Amid/找到值为
15、x的元素，mid即为其下标，返回mid 8 then return mid 9 else if x Amid/如果x Amid，则x可能位于low与mid之间， 10 /否则x可能位于mid与high之间 11 then high mid - 1 12 else low mid + 1 13 14 retrun 0,非递归形式,四、算法的证明 假定在A9中顺序存放着以下9个元素：-15，-6，0，7，9，23，54，82，101。要求检索下列x的值：101，-14和82是否在A中出现。,从算法中可以看到,所有的运算基本上都是进行比较和数据传送，前两条是赋值语句,频率计数均为1。在while循环中，我们集中考虑循环的次数，而其他运算的频率计数显然与这些元素比较运算的频率计数具有相同的数量级，找到这九个元素中的每一个所需的元素循环的次数如下：,五、时间复杂性分析 (1) (log n) (log n) (log n) (log n) (log n),分析：对于A中的n个数，如果x在A中出现，则是成功检索，所以成功检索共有n种情况，而不成功的检索，x将取n+1个区间中的不同值，因此在计算出x在这2n+1种情况下的执行时间后，就可以求出其在各种情况下的时间复杂性了。,例子：A： （1） （2） （3） （4） （5） （6） （7） （8 ） （9 ） 元素： -15 -6 0 7
