计算机算法设计与分析.ppt

1、第一章 绪论,计算机与软件学院（School of Computer and Software）,Nanjing University of Information Science 而算法是有穷的.例 程序是用程序设计语言描述,在机器上可以执行; 而算法还可以用框图、自然语言等多种方式描述.,例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,描述算法可以有多种方式 自然语言、流程图、伪语言等.,三、算法的描述,表达算法的抽象机制,伪语言接近高级语言，易学、

2、易掌握；使得设计出来的算法可读性好，可维护性强，可靠性高； 伪语言算法易于转换为高级语言程序。,算法书写注意点:,1、算法说明：通常在算法头部之下以注释指明：算法功能、参数含义及输入输出属性；算法引用的全局变量或外部变量、其作用、初值及应满足的限制条件等。 2、适当的注释； 3、输入与输出：(1) scanf()、printf() ;(2) 函数参数;(3) 全局变量。 4、错误处理：(1)函数返回状态；(2)内部出错处理。 5、算法结构与语句选用： （1）分支、循环结构：if (switch)、while ( for ) （2）尽量避免用： do do while while 或： if (

3、 ) if ( ) if ( ) 等结构。,Status ListInsert_Sq( SqList / ListInsert_Sq,举例：顺序表插入操作算法描述:,四、算法与数据结构,算法与数据结构的关系 不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂； 反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。 算法数据结构程序,1.2 衡量算法性能的标准,(1)正确性(correctness)执行结果应当满足功能要求。 (2)可读性(readability)为了人的阅读和交流。要求算法易于理解，便于分析。 (3)健壮性(robustness

4、)输入非法数据也能适当地作出反应或进行处理。也称“鲁棒性”。 (4)效率与低存储量高效率、低存储 我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。,时间复杂度（Time Complexity） 算法的时间复杂度：在算法运行期间所花费的时间。 通常用渐进形式表示 例如，T(n)= O (n2)、 (n2) 、 (n2) 空间复杂度（Space Complexity） 算法的空间复杂度：在算法运行期间所需要的辅助内存空间（auxiliary space, or work space）。 通常用渐进形式表示 例如，S(n)= O (n2)、 (n2

5、) 、 (n2),1.3 算法的时间和空间复杂度,1.4 算法分析,算法分析：对于算法的时间和空间复杂度进行定量分析。,一、分析时间复杂度的基本步骤,Step 1、计算出在算法运行期间基本运算执行的总频数. Step 2、表示为渐近时间复杂度（asymptotic time complexity）,二、渐近符号,1. 定义(大“O”符号,增长阶上界) ： 若存在两个正的常数c和n0,对于任意n0,都有T(n)cf(n)，则称T(n)的增长阶不超过f(n)的增长阶,记为T(n)=O(f(n).,例：,(1) 设f(n)=3n,g(n)=n.因对所有n1,有3n4n,(c=4,n0=1),所以有f

6、(n)=O(g(n).,(2) 设f(n)=n+10,g(n)=n.因对所有n1,有n+1011n, (c=11,n0=1),所以有f(n)=O(g(n).,(3) 设f(n)=2n2+11n-10,g(n)=n2.因对所有n10,有2n2+11n-103n2, (c=3,n0=10),所以有f(n)=O(g(n).,(4) 设f(n)=n2,g(n)=n3.因对所有n1,有n2n3, (c=1,n0=1),所以有f(n)=O(g(n).,注意到,满足“O”符号定义的函数f(n)并不是唯一的。所以有以下约定：一个函数增长阶的上界是该函数的所有上界中的最小者(忽略常数因子和低次项).,例:百鸡问

7、题. “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”,a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程： a+b+c=100 5a+3b+c/3=100 c%3=0,第一种解法： a、b、c的可能取值范围：0 100，对在此范围内的 a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。,第二种解法：公鸡只数：n/5;母鸡只数：n/3;小鸡只数：n-a-b。 算法：改进的百鸡问题 输入：所购买的三种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s 1. chicken_problem(int n,int

8、14. 15. 16. 17. ,算法chicken_problem的时间花费： 取n0=28，对 ，有： 令：c=13，并令 ，有： 所以,含义： 的增长最多象 的增长那样快。 称 是 的上界。,运行时间的上界,“O”,2. 大符号(增长阶下界),定义 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cg(n)，则称T(n)的增长阶不小于f(n)的增长阶,记为T(n)=(g(n),例：,设T(n)=3n2+2n,求其增长阶的下界.,因对所有n1,有|T(n)|=|3n2+2n|3n2, (c=3,n0=1),所以有T(n)=(n2).,注意到,满足“”符号定义的函数f(n)并不是唯一

9、的。所以有以下约定：一个函数增长阶的下界是该函数的所有下界中的最大者(忽略常数因子和低次项).,例：百鸡问题chicken_problem算法第10、 11、12、13行，仅在条件成立时才执行,其执行次数未知.假定条件都不成立,这些语句一次也没有执行.所以该算法的执行时间至少为： 当取 = 1时， ，存在常数 ，和函数 ，使得： 所以： T(n)=(n2).,含义： 的增长至少象 的增长那样快。 表示一个解决问题的算法的时间下界。,运行时间的下界,“”,3. 符号(增长阶相同,“渐进的紧的界”),定义 若既有T(n)=O(f(n),又有T(n)=(g(n) ,则称函数T(n)的增长阶等于f(n

10、)的增长阶,记为T(n)= (f(n),例： T(n)5n28n1 当n1时，5n28n15n28nn 5n29n5n29n214n2O(n2) 当n1时，5n28n15n2(n2) 当n1时，14n25n28n15n2 则：5n28n1(n2),例，百鸡问题chicken_problem算法，运行时间的上界是 ，下界是 ；这表明无论输入规模如何变化，该算法的运行时间都介于 和 之间。表明该算法运行时间的准确界是 。,含义： 的增长与 的增长有同样的阶。 表明算法的运行时间有一个较准确的界 。,运行时间的准确界,“”,定理 设f , g是两个函数, , 若r为0的常数, 则 f(n)= (g(

11、n).,证：设r=c为0的常数.由极限的定义可知,取 为c/2,则必存在某个n0,当nn0时, 总在c/23c/2之间. 于是,对 所有 nn0时, f(n) ,从而 f(n)=O(g(n). 并且对所有 nn0,有f(n) ,从而 f(n)=(g(n).,渐近符号的性质,(1) 和函数(对、 也成立) O(f(n)+O(g(n) = O(maxf(n),g(n) ； O(f(n)+O(g(n) = O(f(n)+g(n) ； (2)传递性(对、 也成立) f(n)= O(g(n)， g(n)= O (h(n) f(n)= O (h(n) (3)乘积(对、 也成立) O(f(n)*O(g(n)

12、 = O(f(n)*g(n) O(cf(n) = O(f(n),两个函数f、g增长阶的比较定义了这两个函数之间的一个二元关系.具有的性质:,性质O(f(n)+O(g(n) = O(maxf(n),g(n) 的证明： 对于任意f1(n) = O(f(n) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1f(n) 。 类似地，对于任意g1(n) = O(g(n) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n) 。 令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。 则对所有的 n n3，有 f1(n)

13、 +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .,(4)自反性 f(n)= (f(n) f(n)= O(f(n) f(n)= (f(n) (5)对称性 f(n)= (g(n) g(n)= (f(n) (6)反对称性 f(n)= O(g(n) g(n)= (f(n),增长阶的极限形式判别法,定理 设f , g是两个函数, , 则,(1) c0,f(n)与g(n)同阶,f(n)= (g(n) (2) c=0,f(n)比g(n)低阶,f(n)=O(

14、g(n) (3) c=,f(n)与g(n)高阶, f(n)=(g(n),三、算法时间复杂度的有关概念,最好时间复杂度： 指算法对所有可能输入集的最小执行时间 最坏时间复杂度： 指算法对所有可能输入集的最大执行时间 平均时间复杂度： 指算法对所有可能输入集的执行时间的平均值,对于算法的时间复杂度，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。,例 顺序查找算法 以元素的比较作为基本操作。考虑成功检索的情况。 最好情况下的时间复杂度： (1) 最坏情况下的时间复杂度： (n) 在等概率前提下，平均情况下的时间复杂度： (n),int search(int a ,int n,int key)

15、 for (i=0;in;i+) if (ai=key) return i; return -1; ,四、算法分析中常见的复杂度函数,各种数量级的f(n),五、算法渐近分析的步骤,统计基本操作次数,简化、得到统计结果,基本概念： 渐近复杂度：O, , 平均时间复杂度, 最坏时间复杂度,最好时间复杂度 基本技术： 常用求和公式 递归方程求解,基本技术： 根据循环统计基本操作次数 用递归关系统计基本操作次数,统计基本操作次数的常用方法 根据循环统计基本操作的次数 利用递归关系求基本操作的次数,例：选择排序,void sele_sort(int A ,int n) for (i=0;in-1;i+)

16、 index=i; for (j=i+1;jn;j+) if (AjAindex) index=j; if (index!=i) temp=Aindex; Aindex=Ai; Ai=temp; ,T(n)=n*(1+(n+1)/2+1)= (n2 + 5) /2,T1(n) = n,T2(n) = 1,T3(n) = (n+1)/2,T4(n) = 1,例2 利用递归关系来基本操作的次数. 求Fibonacci数列的第n项。该数列的定义为： F0= F1=1, Fi= Fi-1 + Fi-2，i =2。 由这一数学定义自然地导出一个递归算法。 int F(int n) if(n=0|n=1)

17、 return 1; else if(n=2) return F(n-1)+F(n-2); ,该算法的计算时间T(n)满足递归方程： T(n)=T(n-1)+T(n-2)+1, n1； 初始条件T(0)=T(1)=0。,六、常用求和公式,(1)算术级数,(2)多项式级数,平方和级数,k方和级数,(3) 几何级数,(4)算术-几何级数,也称递推方程（recurrence equation） 是自然数n上一个函数T(n)，它使用一个或多个小于n时的值的等式或不等式来描述。递推方程也称为递推关系或递推式。 递推方程必须有一个初始条件（也称边界条件）。,七、解递归方程,例 逆序输出正整数的各位数. v

18、oid PrintDigit(unsigned int n) printf(n%10);/输出最后一位数dk if(n=10) PrintDigit(n/10); /以逆序输出前k-1位数 ,时间分析 设n = d1d2dk是k位数，当k = 1时，只执行printf语句和if判定语句；当n至少是2位数（k1）时，除了执行这两个操作外，还需执行递归函数调用PrintDigit(n/10)，n/10是k 1位数 。,T(k) = 2k + 2 = (k),迭代法(展开法) 将递归方程的的右端项通过迭代展开成级数,然后估计级数和的渐进阶. 生成函数(母函数)法 替换法 先估计递归方程的显式解,再用

19、数学归纳法证明. 主方法 若递归方程形如:T(n)=aT(n/b)+ f(n),可根据f(n)的不同情况使用主定理.,常用方法：,1、展开法(Recursively expand) 将递归方程展开直到方程右边不再含有未知函数T，而代之以一个级数，对这个级数求和即可得到方程的解。,例：T(n) = 2T(n/2) + 5n2, (设n=2k); T(1) = 7 解：由原方程可得 T(n/2)=2T(n/4)+5(n/2)2 T（n/4）=2T(n/8)+5(n/4)2 . T（n/2k-1）=2T(n/2k)+5(n/2k-1)2 代入原方程，得：,=,= 10n2-3n,例 使用迭代法分析程

20、序。,算法汉诺塔算法 1 void Hanoi(int n, char A, char B, char C) 2 3 if (n=1) Move(A, C); /Move是一个抽象操作，表示将碟子从A移到C上 4 else 5 Hanoi(n-1, A, C, B); 6 Move(A, C); 7 Hanoi(n-1, B, A, C); 8 9 ,分析 函数Hanoi中两次调用自身，函数调用使用的实在参数均为 n 1，函数Move所需时间具有常数界(1)，可将其视为一个程序步，于是有：,扩展并计算此递推式： T(n) = 2T(n 1) + 1 = 2(2T(n 2) + 1) + 1 =

21、 22T(n 2) + 2 + 1 = 23T(n 3) + 22 + 2 + 1 = 2n1T(1) + + 22 + 2 + 1 = 2n1 + + 22 + 2 + 1 = 2n 1,使用递归树（recursion tree）可以形象地看到递推式的迭代过程。 例 T(n) = 2T(n/2) + n的递归树,2、用生成函数(母函数)解递归函数,1) 生成函数的定义 定义: 令 是一个数列,构造如下的函数： 该函数称为数列 a0, a1, a2, 的生成函数. 例：函数 是序列 的生成函数。,2) 生成函数的性质,(1) 加法 设 是序列 的生成函数， 是序列 的生成函数. 则 是序列 的

22、生成函数。,(2) 移位 设 是序列 的生成函数，则 是序列 的生成函数。,(3) 乘法 设 是序列 的生成函数， 是序列 的生成函数， 则 是序列 的生成函数， 其中，,(4) z变换 设 是序列 的生成函数， 则 是序列 的生成函数。,当 时，有： (式1) 则 是序列1,1,1,的生成函数。,特别地，有： 所以， 是序列 的 生成函数。,若取数列为算法的时间复杂度函数 T(n) ,则其生成函数为: f(x)=T(0)+T(1) x+ T(n) xn 如果能由T(n)的递归方程求出T(n)的生成函数,则其展开式第n项系数即为T(n).,3) 用生成函数法求解递归方程,例 汉诺塔(Hanoi

23、)问题。 递归关系式： (式2) 用 作为系数，构造一个生成函数： 令：,(根据式2,h(n)-2h(n-1)=1),由式1，得： 所以： 令： 有： 解得：,所以： 有： ，它是式中第 项的系数。,替换方法要求首先猜测递推式的解，然后用归纳法证明。 例 使用替换方法分析程序Hanoi问题的时间。 可以先对以下这些小的示例进行计算： T(3) = 7 = 23 1；T(4) = 15 = 24 1； T(5) = 31 = 25 1；T(6) = 63 = 26 1 总结规律，猜测：T(n) = 2n 1，n1。,3、替换法,证明：（归纳法证明） (1) 当n = 1时，h(1) = 1，结论

24、成立。 (2) 归纳法假设：当kn时，有h(k) = 2k 1. (3) 那么，当k = n时，h(n) = 2h(n 1) + 1 = 2(2n1 1) + 1 = 2n 1。 因此，对所有n1，h(n) = 2n 1 = (2n)。,4、主方法,主方法 在递归算法分析中，常需求解如下形式的递推式： T(n) = aT(n/c) + f(n) 式中， a1和c1是常数，f(n)是一个渐近正函数，n/c指n/c 或 n/c。 求解这类递推式的方法称为主方法。,定理 设a,b,c为非负常数 , 其中n是c的幂，则其解是：,(主定理),例 T(n) = 16T(n/4) + n T(1)=1 对照

25、公式: a=16,c=4,b=1,符合情况（3）， 例 T(n) = 2T(n/2) + n 对照公式: a=2,c=2,b=1,符合情况（2）， 例 T(n) = 3T(n/4) + n 对照公式: a=3,c=4,b=1,符合情况（1）,1.5 最优算法(optimal algorithm),一、问题的下界,定义 一个问题的下界是解决该问题的任意算法所需要的最小时间复杂度。,注: 定义中的时间复杂度指最坏时间复杂度.,首先对已知的解决该问题的算法进行分析,找出同类算法中共有的基本操作的最大集合. 再证明这些基本操作(或其中的一些基本操作构成的子集)在最坏情况下对于该问题的解决是必不可少的.

26、,问题下界的确定?,例，在一个无序数组中查找最大元的算法.,输入：数组E ,数组大小n. 输出：最大元素max. int findMax(int E, int n) int max; max = E0; / Assume max. for (index = 1; index n; index+) if (max Eindex) max = Eindex return max; ,算法findMax的最好、最坏和平均时间复杂度都一样，为(n).,查找无序数组最大元的所有算法的时间复杂度的下界是否是(n)?,分析：不失一般性,只考虑数组中各元素互不相同的情形.因此n元数组中最大元只有一个.对其余n

27、-1个元素,要判定它不是最大元,至少要找到一个比它大的元素,因此需要至少一次比较.所以,为了找出最大元,任何算法至少需要n-1次比较.由此可确定查找最大元问题的算法复杂度下界为(n).,定义 如果一个算法的时间复杂度等于这个问题的下界，那么该算法是最优的。,二、最优算法,例，算法findMax即为最优算法.,例如，排序问题的计算时间下界为(nlogn)，时间复杂度为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。,1.6 高效算法的必要性,例：设算法A在输入规模为n时的计算时间为T(n)=3 2n.在计算机C1上执行该算法的算法是t秒.现有另一台计算机C2,其运行速度是C1的64

28、倍,则在C2上用算法A在t秒内能解输入规模为多大的问题?若算法的计算时间改进为T(n)=n2,其余条件不变,则在C2上用t秒内能解输入规模为多大的问题?,解：设C2用算法A在t秒内能解n1规模的问题.则有 ,得n1=n+6. 设C2用改进算法在t秒内能解n2规模的问题.则有 ,得n2=8n.,不同时间复杂度下不同输入规模的算法运行时间 ,这里假定每一个操作时间是1ns.,n：纳秒 ：微秒 ms：毫秒 s：秒 h：小时 d：天 y：年 c：世纪,计算机速度提高10倍后,不同算法复杂度求解规模的扩大情况,Faster Computer or Faster Algorithm?,附录:基本数据结构复

29、习,线性结构 线性表 栈 队列 串 非线性结构 树，二叉树 图,（a1, a2, ai-1，ai, ai1 ，, an）,(一) 线性表有关的概念：,数据元素,表头,ai的直接前驱,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,表尾,n=0时称为空表,在数据元素的非空有限集中： （1）存在唯一的一个被称为“第一个”的数据元素（开始结点）； （2）存在唯一的一个被称为“最后一个”的数据元素（终端结点）； （3）除第一个之外，每个数据元素均只有一个前驱； （4）除最后一个之外，每个数据元素均只有一个后继 .,线性表的特点：,线性表的顺序存储结构,Locate(a

30、i+1) = Locate(ai) + sizeof(ElemType) Locate(ai) = Locate(a1) + sizeof(ElemType) *( i-1),单链表,用一组任意的存储单元存储线性表的各个数据元素。 数据元素之间的关系通过保存直接后继元素的存储位置来表示。,线性表的链式存储和实现,栈 - 是限制仅在线性表的一端进行插入和删除运算的线性表。 栈顶（top）-允许插入和删除的一端。 栈底（bottom)-不允许插入和删除的一端。 空栈-表中没有元素。,栈的特点： 后进先出 (LIFO),特殊的线性表栈,定义：队列是只允许在一端删除，在另一端插入的线性表。 队头(front)： 指允许删除的一端 。 队尾(r