《数据结构与数据库》PPT课件.ppt

1、数据结构与数据库,第一部分 数据结构,教材 数据结构（c语言版），严蔚敏等编著,清华大学出版社，1997 数据结构题集（c语言版），严蔚敏等编著,清华大学出版社，1999,参考书 数据结构(第二版)，唐策善、黄刘生 编著，中国科大出版社，2001 Data Structures with C+, Williaw Ford et al., Prentice Hall Inc., 1996. Data Structures i n-1; i+ ) /n-1趟 从ai检查到an-1;若最小整数在ak, 交换ai与ak; 细化：Select Sort,void selectSort ( int a ,

2、 int n ) /对n个整数a0,a1,an-1按递增顺序排序 for ( int i = 0; i n-1; i+ ) int k = i; for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; /从ai查到an-1, 找最小整数, 在ak int temp = ai; ai = ak; ak = temp; ,性能分析与度量,算法的性能标准 正确性 可读性 健壮性 效率（时间、空间）,算法的事后统计（后期测试） 在算法中的某些部位插装时间函数time ( ), 测定算法完成某一功能所花费时间 double start, stop; time (

3、,int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索x int i = 0; while ( i n ,算法的事前估计 时间复杂度度量 运行时间 = 算法中每条语句执行时间之和。 每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。 语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。 设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。,举例 1,矩阵相乘算法 for ( i =1; i=n;+i ) / n+1 for (j =1;j=n;+j) /n(

4、n+1) c i j = 0; /n2 for ( k=1;k=n;+k) /n2(n+1) c i j +=a i k *b k j ; /n3 则 算法执行时间T(n)为所有语句的频度之和。 T(n) = n+1+n(n+1)+n3 = 2n3 +3n2+2n+1,渐进时间复杂度 引入“O”记号，以体现随问题规模n的增长率。 T(n) = n+1+n(n+1)+n3 = 2n3 +3n2+2n+1 O(n3)，其中n3 为增长最快的项。 最坏时间复杂度 vs. 平均时间复杂度 有时算法基本操作重复执行次数还随问题的输入数据集不同而不同（如一些排序算法）。 这时可分析最坏时间复杂度（最坏情况

5、下的时间复杂度）和平均时间复杂度（平均情况下的时间复杂度）,估计算法时间的通常做法： 根据问题（或算法类型），从算法中选取一种原操作（指固有数据类型的操作）作为基本操作。 其重复执行次数应与算法执行时间成正比； 一般为最深层循环内的语句中的原操作； 用该基本操作重复执行的次数作为算法的时间度量。即统计包含该操作的所有语句的频度之和。 如：上例中选取乘法为基本操作；算法执行时间 T(n)则正比于乘法所在语句的频度n3 ,记为T(n) = O(n3),试估计以下程序段 的时间复杂度 for ( i =1; i=n ; + i) for (j =1; j=i ; +j) for(k =1;k=j;+k) x+ 基本操作执行次数为 因此 T(n)=O(n3),举例 2,空间复杂度度量 存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间 空间复杂度 原地工作（额外空间相对输入数据量来说是常数）,常见时间复杂度,O(1) 常数阶 O(n) 线性阶 O(n2) 平方阶