《第一章算法设计基本方法.ppt》由会员分享，可在线阅读，更多相关《第一章算法设计基本方法.ppt（43页珍藏版）》请在三一文库上搜索。
1、算法设计基本方法（1）,列举法(穷举法): 指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。 例：百鸡问题（教材p6）,特点：算法简单，可读性强，直观易于理解和设计 适用范围：解决“是否存在”或者“有多少种可能”问题 缺点：运算工作量巨大 改进方法：分析实际问题，缩小列举范围以减少运算量 软肋：不能用以解决列举量无限的问题,或列举量非常大的问题,算法设计基本方法（2）,归纳法： 通过分析少量特殊情况，找出关系，得到结论 例：搏彩问题,这期彩票该买几呢？,根据曲线，买5比较好,归纳法,特点：适用面广，高效使用，常能解决许多实际
2、问题 适用范围：样本空间有一定规律，多用于预测领域，数据难以获得的工程计算科学计算等领域 缺点：归纳出的数学模型需要证明，且代码实现不规范 改进方法：常采用不同归纳方法共同求解一个问题 软肋：不能求解样本空间过于零散的问题,算法设计基本方法（3）,递推 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果 特点：采用递推关系式数学模型，理论正确性得到保证，由于递推关系式来源于归纳，所以本质上属于归纳法 适用范围：数值计算等工程应用 缺点：需考虑数值计算中稳定性问题，易产生蝴蝶效应 软肋：无递推关系式的问题不可解,NY,BJ,递推,据说，美军 1910 年的一次部队的命令传递是这样的: 营
3、长对值班军官: 明晚大约 8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔 76年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。 值班军官对连长: 根据营长的命令，明晚8点哈雷彗星将在操场上空出现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。 连长对排长: 根据营长的命令，明晚8点，非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔76年才会出现一次。 排长对班长: 明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔 76年才有的
4、事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。 班长对士兵: 在明晚8点下雨的时候，著名的76岁哈雷将军将在营长的陪同下身着野战服，开着他那“彗星”牌汽车，经过操场前往礼堂。,例：计算, 公式一：,?,?,? !,! !,What happened?!,注意此公式精确成立,考察第n步的误差, 公式二：,注意此公式与公式一 在理论上等价。,方法：先估计一个IN ,再反推要求的In ( n N )。,可取,取,考察反推一步的误差：,以此类推，对 n N 有：,误差逐步递减, 这样的算法称为稳定的算法 /* stable algorithm */,类似例子见教材p8,算法设计基本方法（4）,
5、递归 将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。,例： 计算阶乘: n! = n(n1) 21, 0! = 1.,int factorial ( int n ) int i, result; result =1; if ( n 0 ) for ( i = 1; i = n; i+ ) result = result * i ; /* end if */ return result; ,int factorial ( int n ) if ( n 0 ) return n * factorial ( n
6、 1 ); else return 1; ,例:斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 + Fi-2 （i1) 算法 求斐波那契数 int F(n) /返回第n个斐波那契数/ int n; if (n= 1) return(1); else return F(n-1) + F(n-2); 算法效率：对F(n-1) 、F(n-2)存在大量的重复计算 改 进：保存中间结果,例 :欧几里得算法 已知两个非负整数a和b，且ab0，求这两个数的最大公因数。 辗转相除法：若b=0，则a和b的最大公因数等于a；若b0，则a和b的最大公因数等于b和用b除a的余数的最大
7、公因数。 算法 求最大公因数 GCD(int a,int b) / 约定ab / if (b=0) return(a); else return (GCD(b,a % b); 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,递归,特点：结构清晰，可读性强，容易用数学归纳法证明算法正确性 适用范围：难以用循环或递推直观描述的复杂问题 缺点：资源耗费多，执行效率低，所以在算法优化时采用消递归策略,算法设计基本方法（5）,减半递推技术（分治法） 所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。,例：二分
8、法求方程实根的减半递推过程（算法及程序见书p13） 首先取给定区间的中点c(ab)/2。 然后判断f(c)是否为0。 若f(c)0,则说明c即为所求的根，求解过程结束； 如果f(c)0,则根据以下原则将原区间减半： 若f(a)f(c)0，则取原区间的前半部分； 若f(b)f(c)0，则取原区间的后半部分。 最后判断减半后的区间长度是否已经很小： 若|ab|，则过程结束，取(ab)/2为根的近似值； 若|ab|，则重复上述的减半过程。,例 二分检索 二分检索：每次选取中间元素的下标,算法 二分检索 Int BINSRCH(int A,int n,int x) int low,high,mid;
9、low=1; high=n; while (lowAmid) low =mid+1; else return mid; return 0; ,注： 给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。 若是，返回当前角标mid 若非，返回0，表示没有找到,例：设A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中检索x=101，-14，82。执行轨迹见下表1,成功的检索,不成功的检索,成功的检索,递推减半技术,特点：迅速缩小计算规模 适用范围：工程计算，矩阵计算，数值计算中能够迅速将问题分治的情况,算法设计基本方法（6）,回溯法 通过对问题的分析，找出一
10、个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。 例：八皇后问题（教材p15）迷宫问题 实际上是一种图的深度优先遍历的方法 特点：算法效率高，直观清楚 适用范围：适用于解决“是否存在”或者“有多少种可能”问题 缺点：算法的复杂性与计算顺序有关,算法分析,1. 分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。 算法分析是计算机领域的“古老”而“前沿”的课题。,算法分析,“好”的算法应当达到以下
11、指标 正确性(Correctness):算法应当满足具体问题的需求 可读性(Readability):算法是连接数学模型和程序的桥梁,可读性好有助于人对算法的理解 健壮性(Robustness):算法对于异常情况有充分的考虑和处理方法 效率高和存储量少: 时间复杂度:指执行算法所需要的计算工作量 算法的工作量f(n) 空间复杂度:执行算法所需要的内存空间,n指算法规模,时间复杂度(1),平均性态(average behavior): 用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量,最坏情况复杂性 (WorstCase Complexity) 规模在n时,算法所执行的基本运算的最大
12、次数,由于最坏情况复杂性给出算法工作量的一个上界,所以更具实用价值,时间复杂度(2),例:顺序搜索法的时间复杂度分析(教材p17) 采用顺序搜索法，在长度为n的一维数组中查找为x的元素。 算法:即从数组的第一个元素开始，逐个与被查值x进行比较。 基本运算:x与数组元素的比较。,平均性态分析:,最坏情况分析: W(n)maxti | 1in1n,如何进行算法分析？ 对算法进行全面分析，可分两个阶段进行： 事前分析：求算法的一个时间/空间限界函数，即通过对算 法的“理论”分析，得出关于算法时间和空间特性 的特征函数（、）与计算机物理软硬 件没有直接关系。 事后测试：将算法编制成程序后实际放到计算机
13、上运行， 收集其执行时间和空间占用等统计资料，进行 分析判断直接与物理实现有关。,1）事前分析 目的：试图得出关于算法特性的一种形式描 述（限界函数），以“理论上”衡量算法的“好坏”。 如何给出反映算法特性的描述？ 统计算法中各种运算的执行情况，包括： 引用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。 算法的执行时间=fi*ti,工作量 工作量：算法中语句或运算的执行次数。 例： x=x+y for (i=0;in;i+) for (i=0;in;i+) x = x + y for (j=0;jn;j+) x = x +y (a) (b) (c) 分析： (a)： x=x
14、+y执行了1次 (b)： x=x+y执行了n次 (c)： x=x+y执行了n2次,限界函数的表示 就计算时间而言，事前分析阶段求得算法在工作量 上的算法规模n的函数称为限界函数，记为： g(n) 限界函数以算法中主要运算单元为基本运算统计运算次数的数量级 g(n)的一般形式：关于n的简单函数式 g(n)用以限界，因此只采用所得到计算次数的最高次项表示：随着n（规模）的增大，多项式函数式的最高次项的变化能够最显著的反映整个多项式的变化 不同的算法，g(n)的具体形式是不同的，常用的限界函数有：1；logn；n；nlogn；n2；n3； nm ；2n；n！；nn等,2）事后测试 目的：运行程序，统
15、计执行实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。 分析手段：作时、空性能分布图,计算时间的渐近表示,记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n) 其中， n是输入或输出规模的某种测度。 f(n)表示算法的“实际”执行时间与机器及语言有关。 g(n)是事前分析的结果一个形式简单的函数，如nm，logn，2n，n!等。是与工作量有关、而与机器及语言无 关的函数。 以下给出算法执行时间：上界（）、下界（）、“平均”（ ）的定义。,1）上界函数,定义1 如果存在两个正常数c和n0，对于所有的nn0，有 |f
16、(n)| c|g(n)| 则记作f(n) = (g(n) 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。 f(n)的数量级就是g(n)。 试图求出最小的g(n)，使得f(n) = (g(n)。,数量级 衡量工作量的“大小”的一种测度，通过f(n)的上界函数g(n)确定 语句的数量级：语句的执行次数 例：1，n ，n2 算法的数量级：算法所包含的所有语句的执行次数之和。 数量级反映了算法复杂度的最本质的特征。 例：假如求解同一个问题的三个算法分别具有n， n2 ， n3数量级。次数 若n=10，
17、则可能的执行时间将分别是10，100，1000个单位时间与环境因素无关。,计算时间的数量级的大小对算法有决定性的影响 例：假设解决同一个问题的两个算法，它们都有n个输入, 计算时间的数量级分别是n2和nlogn。则， n=1024：分别需要1048576和10240次运算。 n=2048：分别需要4194304和22528次运算。 分析： 同等规模下的计算量比较： 规模增大情况下的比较：在n加倍的情况下，一个(n2)的算法计算时间增长4倍，而一个(nlogn)算法则只用两倍多一点的时间即可完成。,多项式时间算法和指数时间算法,多项式时间算法：可用多项式（函数）对其计算时间限界 的算法。 常见的
18、多项式限界函数有： (1) (logn) (n) (nlogn) (n2) (n3) 指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数： (2n) (n！) (nn) 说明：当n取值较大时，指数时间算法和多项式时间算法在计算时 间上非常悬殊。,典型的计算时间函数曲线,一般认识 当数据集的规模很大时，要在现有的计算机系统上运行 具有比(nlogn)复杂度还高的算法是比较困难的。 指数时间算法只有在n取值非常小时才实用。 要想在顺序处理机上扩大所处理问题的规模，有效的途径 是降低算法的计算复杂度，而不是（仅仅依靠）提高计算 机的速度。,计算时间函数值比较,3,常见时间复杂度数量级
19、分析（1）,常见时间复杂度数量级分析（2）,定义1.2 如果存在两个正常数c和n0，对于所有的nn0， 有 |f(n)| c|g(n)| 则记作f(n) = (g(n) 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。 试图求出“最大”的g(n)，使得f(n) = (g(n)。,2）下界函数,定义1.3 如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)| 则记作 含义： 算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作
20、： 既有 f(n) = (g(n)，又有f(n) = (g(n),3）“平均情况”限界函数,空间复杂度,算法占用空间 算法程序空间 输入数据空间 算法执行的额外空间,由于算法执行空间是可以在算法设计中优化的，所以往往通过压缩等方法缩小这方面的空间占用,如果相对与程序规模，其执行的额外空间为常数级，则称算法为原地工作（in place）,小结,算法:解题方案准确而完整的描述.是连接数学模型和程序的纽带. 算法性质: 能行性 确定性 有穷性 拥有足够信息 算法要素: 对数据的运算和操作 算法的控制结构,算法描述:算法描述语言中包含符号与表达式、赋值语句、控制转移语句、循环语句、输入输出终止等其他语句 算法设计方法： 列举法 归纳法 递推 递归 减半递推技术 回溯法,算法分析: 时间复杂度 平均性态 最坏情况复杂性 空间复杂度 算法程序空间 输入空间 算法执行的额外空间 时间复杂度种类(按优劣排)： O(1),O(log2n),O(n),O(n2), O(n3),O(2n),Homework,教材p19 习题1.1,1.2,