2009年数据结构2PPT课件

1、2021/3/912021/3/922021/3/932021/3/942021/3/952021/3/962021/3/972021/3/982021/3/992021/3/910欧欧几几里里德德算算法法 输入输入m 和和n； 求求m除以除以n的余数的余数r； 若若r等于等于0 0，则，则n为最大公约数，算法结束；为最大公约数，算法结束；否则执行第否则执行第步；步； 将将n的值放在的值放在m中，将中，将r的值放在的值放在n中；中； 重新执行第重新执行第步。步。自然语言N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y流 程 图2021/3/911#include int Co

2、mmonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n;void main( ) coutCommonFactor(63, 54)endl;程序设计语言欧几里德算法欧几里德算法2021/3/9121.4.2 算法设计的要求算法设计的要求评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准:(1)正确性正确性(Correctness ) 算法应满足具体问题的需求。算法应满足具体问题的需求。(2)可读性可读性(Readability) 算法应该好读。以有利于阅读者对程算法应该好读。以有利于

3、阅读者对程序的理解。序的理解。(3)健状性健状性(Robustness) 算法应具有容错处理。当输入非法数据算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。时，算法应对其作出反应，而不是产生莫名其妙的输出结果。(4)效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量需效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。问题的规模有关。2021/3/9131.4.3 算法效率的度量算法效率的度量 对一个算法执行时间的分析，有两种方法，即

4、对一个算法执行时间的分析，有两种方法，即事先分析估事先分析估算方法算方法和和事后统计方法事后统计方法 事先分析事先分析 求出该算法的一个时间界限函数求出该算法的一个时间界限函数,作为对算法所消作为对算法所消耗资源的一种估算方法。耗资源的一种估算方法。 事后统计事后统计 收集此算法的执行时间和实际占用空间的统计资收集此算法的执行时间和实际占用空间的统计资料。缺点：料。缺点： 编写程序实现算法将花费较多的时间和精力；编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素。所得实验结果依赖于计算机的软硬件等环境因素。 一般情况下，算法中基本操作一般情况下，算法中基本操作

5、(固有的数据类型操作固有的数据类型操作)重复执重复执行的次数是问题规模行的次数是问题规模n的某个函数，算法的时间量度记作：的某个函数，算法的时间量度记作： T(n)=O(f(n)称作算法的渐近时间复杂度。称作算法的渐近时间复杂度。2021/3/914定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有都有T( (n)cf( (n) )，则称，则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之前的情之前的情况无关紧要况无关紧要T( (n) )cf( (n) )大大O符号符号2021/3/915例、例、for(i=1，i=n;

6、+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，则总次数为，则总次数为: nnn=n3时间复杂度为时间复杂度为T(n)=O(n3)它代表算法执行时间的增长率和它代表算法执行时间的增长率和n3的增长率相同。的增长率相同。2021/3/916 所选基本操作执行的次数与算法的执行时间应成正比，一所选基本操作执行的次数与算法的执行时间应成正比，一般它是最深层循环内的语句中的基本操作。它的执行次数和包般它是最深层循环内的语句中的基本操作。它的执行次数和包含它的语句的频度

7、相同。含它的语句的频度相同。频度频度：是指该语句重复执行的次数：是指该语句重复执行的次数例例 +x;s=0;，将，将x自增看成是基本操作，则语句频度为，自增看成是基本操作，则语句频度为，即时间复杂度为即时间复杂度为(1)如果将如果将s=0也看成是基本操作，则语句频度为，其时间复杂也看成是基本操作，则语句频度为，其时间复杂度仍为度仍为(1)，即常量阶。，即常量阶。例、例、for(i=1;i=n;+i) +x;s+=x; 语句频度为：语句频度为：2n其时间复杂度为：其时间复杂度为：O(n) 即时间复杂度为线性阶。即时间复杂度为线性阶。2021/3/917例、例、for(i=1;i=n;+i)for

8、(j=1;j=n;+j) +x;s+=x; 语句频度为：语句频度为：2n2其时间复杂度为：其时间复杂度为：O(n2)定理：若定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个是一个m次次多项式，则多项式，则A(n)=O(n m)例例for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x;ai，j=x;2021/3/918语句频度为：语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/2=(n-1)(n-2)/2 =n2-3n+2 时间复杂度为时间复杂度为O(n2) 即此算法的时间复杂度为平方阶即此算法的时间复杂度为平方阶. 一个算法时间

9、为一个算法时间为O(1)的算法，它的基本运算执行的次数是的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为界。而一个时间为O(n2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)2021/3/919指数时间的关系为：指数时间的关系为： O(2n)O(n!)1), 2n , 3n nc(c1), n2, n3 n

10、log(n), nlog2(n) nr(0r=1 & change;-i) change=FALSE; for(j=0;jaj+1) aj aj+1; change=TURE 最好情况：基本操作执行最好情况：基本操作执行0次。最坏情况：次。最坏情况：1+2+3+n-1 =n(n-1)/2。平均时间复杂度为。平均时间复杂度为:O(n2) 2021/3/9211.4.4算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作:S(n)=O(f(n) 其中其中n为问题的规模为问题的规模(或大小或大小)程序用的存储空间包括固定和可变两个部分：程

11、序用的存储空间包括固定和可变两个部分：1、固定部分：这部分空间的大小与输入输出的个数多少、固定部分：这部分空间的大小与输入输出的个数多少、数值大小无关。主要包括存放程序指令代码的空间，常数值大小无关。主要包括存放程序指令代码的空间，常数、简单变量、定长成分（如数组元素、结构成分等）数、简单变量、定长成分（如数组元素、结构成分等）变量所占的空间等。这部分属于静态空间，只要作简单变量所占的空间等。这部分属于静态空间，只要作简单的统计就可估算。的统计就可估算。2、可变部分：这部分空间主要包括其尺寸与实例特征有、可变部分：这部分空间主要包括其尺寸与实例特征有关的成分变量所占空间、引用变量所占空间、以及递归关的成分变量所占空间、引用变量所占空间、以及递归栈所用的空间，还有算法运行时动态命令使用的空间。栈所用的空间，还有算法运行时动态命令使用的空间。2021/3/9222021/3/923绪绪 论论数据结构数据结构算算 法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据