《chap1 引言 - 浙江大学计算机辅助设计与图形学国家》由会员分享，可在线阅读，更多相关《chap1 引言 - 浙江大学计算机辅助设计与图形学国家（37页珍藏版）》请在金锄头文库上搜索。
1、程序设计专题,Topic4 查找/排序,学习目标,了解算法效率的度量方法和大O记法 掌握简单的线性查找法和二分查找法 掌握简单的选择排序法和冒泡排序法 了解分而治之策略，基本掌握归并排序法,一、算法效率的度量,算法设计的要求 正确性：算法至少应具有输入/出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。 可读性：便于阅读、理解和交流 健壮性：当输入数据不合法时，算法能做出相关处理，而非产生异常或莫名其妙的结果 时间效率高和存储量低 算法效率的度量方法 事后统计方法（有缺点，较少使用） 事前分析估算方法,一、算法效率,算法时间复杂度 与高级语言程序执行时间相关的因素,算法采用的
2、策略、方法 编译产生的代码质量 问题的输入规模 机器执行指令的速度, 软件 硬件, 算法好坏的根本 软件 输入量的多少 硬件,执行 2n+3次,执行 3次,一、算法效率,算法时间复杂度,分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来,执行次数对同样的输入规模，多于前两个算法； 随着n的增加执行次数也将远远多于前面两个 测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。,f(n) = n,f(n) = 1,f(n) = n2,一、算法效率,算法时间复杂度 算法时间复杂度定义,进行算法分析时，一般从算法中选取一种对所研究问题是基本
3、/主要 的原操作（多数情况下取自最深层次循环体内的语句）,以该基本操作在 算法中重复执行的次数T(n)作为算法运行时间的衡量准则。 算法的渐进时间复杂度简称算法的时间复杂度，就是算法的时间度量， 记作T(n)=(f(n) （即大O记法）。表示随问题规模n的增大，算法执行 时间的增长率和f(n)增长率相同（或同数量级的 ）。 T (n) = (f (n) 表示存在一个常数C，使得在当n趋于正无穷时总有 T (n) C * f(n)。简单说就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。 也就是说当n趋于正无穷时T (n)的上界是C * f(n)。 对f(n)没有规定，但f(n) 一般都是
4、取尽可能简单的函数。 例如， O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ),一、算法效率,算法时间复杂度 算法时间复杂度定义,按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.， k次方阶O(nk),指数阶O(2n)，阶乘阶O(n！)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。,一、算法效率,算法时间复杂度 算法时间复杂度实例,T(n)=O(1) Temp=i; i=j; j=temp;,T(n)=
5、 O(log2n) i=1; while (i=n) i=i*2; T(n)=O(n2) for (i=1;in;i+) y=y+1; for (j=0;j=(2*n);j+) x+; ,T(n)=O(n) a=0; b=1; for (i=1;i=n;i+) s=a+b; b=a; a=s; ,一、算法效率,算法时间复杂度,我们要确定能反映出算法在各种情况下工作的数据集, 选取的数据要能够反映、代表各种计算情况下的估算, 包括最好情况下的时间复杂度(时间复杂度下界, 一般记为Tmax)、最坏情况下的时间复杂度(时间复杂度上界, 一般记为Tmin)、平均情况下的时间复杂度(一般记为Tavg)和
6、有代表性的情况, 通过使用这些数据配置来运行算法,以了解算法的性能。 除非特别指定，提到的都是最坏情况时间复杂度,一、算法效率,算法空间复杂度,算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的空间复杂度S(n)算法是对一个算法在运行过程中临时占用存储空间大小的量度。,二、查找算法,线性查找法 二分查找法,查找/检索：在一组数据中找出满足某种条件的数据的过程,int
7、 FindFirstUpperLetter( char * string ) int i; for ( i = 0; i strlen(string); i+ ) if ( isUpper(stringi) ) return i; return -1; ,在一个字符串中查找第一个大写字母的具体方法是什么？,二、查找算法,线性查找法,条件,从第一个元素起逐个元素进行比较,查找/检索：在一组数据中找出满足某种条件的数据的过程,如果ai-1符合查找条件，则找到并停止查找；否则按照前面的步骤继续下去。,条件,如果此时仍然没有找到，返回未找到信息并停止,条件,需定义一个函数int FindInteger
8、InArray（int key, int array,int n)用于在一个有效长度为n的整数数组中查找整数Key。,二、查找算法,线性查找法,/* Example: linear search */ /* 要求编写程序来显示美国的硬币名称和它对应的值*/,查找/检索：在一组数据中找出满足某种条件的数据的过程,static int FindIntegerInArray (int key, int array, int n) int i; for (i = 0; i n; i+) if (key = arrayi) return (i); return (-1); ,需定义一个函数int Fin
9、dIntegerInArray（int key, int array,int n)用于在一个有效长度为n的整数数组中查找整数Key。 若美国的标准硬币有五种，则可用两个数组分别表示币值和币名。,二、查找算法,线性查找法,/* Example: linear search */ /* 要求编写程序来显示美国的硬币名称和它对应的值*/,查找/检索：在一组数据中找出满足某种条件的数据的过程,/* Example: linear search */ /* 要求编写程序来显示美国的硬币名称和它对应的值*/,#include static char* coinNames = “penny”, “nicke
10、l”, dime”, “quarter”, “half-dollar”,; static int coinVlaues = 1, 5, 10, 25, 50; static int nCoins = sizeof coinValues / sizeof coinValues0; static int FindIntegerInArray (int key, int array , int n) ; /* Main program */ main() int value, index; printf (“This program looks up names of U.S. coins.n”);
11、 printf (“Enter coin value: “); scanf (“%d”, ,二、查找算法,二分查找法,查找/检索：在一组数据中找出满足某种条件的数据的过程,线性查找要逐个比较表中元素。当表中元素非常多时，顺序查找的效率是很低的。二分查找在速度方面有所改进，但是只适用于已排好序的数组。,11,11,11,查11 Flag1,二、查找算法,二分查找法,查找/检索：在一组数据中找出满足某种条件的数据的过程,线性查找要逐个比较表中元素。当表中元素非常多时，顺序查找的效率是很低的。二分查找在速度方面有所改进，但是只适用于已排好序的数组。,输 入,2 3 5 7 9 10 11 16,4,
12、4,4,查4 Flag0,/* Example: binary search */ /* 要求在一组整数中查找一个值 */,# include # define N 8 main() int i, aN, searchKey, low, high, middle, flag; for (i=0; iN; i+) ai=2*i; /*create data*/ printf(“Enter interger search key:n”); scanf(“%d”, ,二、查找算法,查找算法的效率,查找/检索：在一组数据中找出满足某种条件的数据的过程,在最坏情况下，线性查找法查找N个元素的数组需要N次
13、比较，而二分查找法需要log2N次比较,N / 2 / 2 / / 2 / 2 = 1,K次,三、排序算法,选择排序法 冒泡排序法 归并排序法,排序：重排一组数据使它们按某一事先确定的顺序存储的过程,对一组数据，每次将其中的一个数据放在它最终要放的位置。第一步是找到整个数据中最小的数据并把它放在最终要放的第一个位置上，第二步是在剩下的数据中找最小的数据并把它放在第二个位置上。对所有数据重复这个过程，最终将得到按从小到大顺序排列的一组数据。,三、排序算法,选择排序法,排序：重排一组数据使它们按某一事先确定的顺序存储的过程,在a0-a6中找最小值ak, 比较后确定k为2; 交换a0ak与的值, 结
14、果： 1 6 2 8 7 4 5,第0次 选择,在a1-a6中找最小值ak, 比较后确定k为2; 交换a1ak与的值, 结果： 1 2 6 8 7 4 5,第1次 选择,在a2-a6中找最小值ak, 比较后确定k为5; 交换a2ak与的值, 结果： 1 2 4 8 7 6 5,第2次 选择,在a3-a6中找最小值ak, 比较后确定k为6; 交换a3ak与的值, 结果： 1 2 4 5 7 6 8,第3次 选择,在a4-a6中找最小值ak, 比较后确定k为5; 交换a4ak与的值, 结果： 1 2 4 5 6 7 8,第4次 选择,在a5-a6中找最小值ak, 比较后确定k为5; 交换a5ak与
15、的值, 结果： 1 2 4 5 6 7 8,第5次 选择,2 6 1 8 7 4 5,三、排序算法,选择排序法,排序：重排一组数据使它们按某一事先确定的顺序存储的过程,/* Example: selection sort */ /* 要求对一组整数进行由小到大的排序*/,for ( i = 0; i N-1 ; i+) 找出aiaN-1之间值最小的数组元素下标k; 交换ai与ak的值； ,k = i; for (j = i+1; jN; j+) if (aj ak) k = j;,# include void main() int i, index, k, n, temp, a10; scanf(“%d”, ,三、排序算法,选择排序法,排序：重排一组数据使它们按某一事先确定的顺序存储的过程,算法效率：,随着N的增大，执行时间显著增加,实验结论：数组的元素个数增加一倍，所需要的时间是原来的4倍。这个算法具有平方律的性质，即执行时间和输入数据的个数的平方成正比。,算法分析：对N个数据排序，需执行N-1次外层for循环：第一次找出N个数中最小值，下一次是在剩
