《数据结构教学课件.ppt》由会员分享,可在线阅读,更多相关《数据结构教学课件.ppt(144页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、10/23/2019,1,IntroductionSpace ComplexityTime ComplexityAsymptotic NotationPractical ComplexitiesPerformance Measurement,Chapter 2 Program Performance,10/23/2019,2,顺序搜索/折半搜索算法名次排序/选择排序/冒泡排序/插入排序算法渐进符号(O、 、 、o),本章重点,10/23/2019,3,算法的性能标准,正确性可使用性可读性健壮性文档效率:对空间和时间的需求,10/23/2019,4,程序性能:运行一个程序所需要的内存和时间。为什
2、么关心程序性能?分析(Analysis)/实验(measurement)空间复杂性(Space Complexity)/时间复杂性(Time Complexity),2.1 Program Performance,10/23/2019,5,指令空间(Instruction space)数据空间(Data space)环境栈空间(Environment stack space),2.2 Space Complexity,10/23/2019,6,程序所需要的指令空间的数量取决于如下因素:把程序编译成机器代码的编译器。编译时实际采用的编译器选项。目标计算机。例子:计算表达式a+b+b*c+(a+b
3、-c)/(a+b)+4 的代码。,指令空间,10/23/2019,7,10/23/2019,8,对于简单变量和常量来说,所需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。由于每字节所占用的位数依赖于具体的机器环境,因此每个变量所需要的空间也会有所不同。,数据空间,10/23/2019,9,每当一个函数被调用时,下面的数据将被保存在环境栈中:返回地址。函数被调用时所有局部变量的值以及传值形式参数的值(仅对于递归函数而言)。所有引用参数及常量引用参数的定义。,环境栈空间,10/23/2019,10,无法精确地分析一个程序所需要的空间。可以确定程序中某些部分的空间需求,这些部分依赖于所解
4、决实例的特征。例:对n 个元素进行排序;累加两个nn 矩阵;累加两个mn 矩阵。,结论,10/23/2019,11,递归函数所需要的栈空间通常称之为递归栈空间(recursion stack space)。对于每个递归函数而言,该空间主要依赖于局部变量及形式参数所需要的空间。除此以外,该空间还依赖于递归的深度(即嵌套递归调用的最大层次)。,递归栈空间,10/23/2019,12,可以把一个程序所需要的空间分成两部分:固定部分,独立于实例的特征。一般来说,这一部分包含指令空间(即代码空间)、简单变量及定长复合变量所占用空间、常量所占用空间等等。可变部分,由以下部分构成:复合变量所需的空间(这些变
5、量的大小依赖于所解决的具体问题),动态分配的空间(这种空间一般都依赖于实例的特征),以及递归栈所需的空间(该空间也依赖于实例的特征)。,空间复杂性度量,10/23/2019,13,任意程序P 所需要的空间S(P)可以表示为:S(P) = c + Sp(实例特征)在分析程序的空间复杂性时,我们将把注意力集中在估算Sp(实例特征)上。对于任意给定的问题,首先需要确定实例的特征以便于估算空间需求。,空间复杂性度量,10/23/2019,14,templateint SequentialSearch(T a, const T,程序2-1 顺序搜索(Sequenial Search),10/23/201
6、9,15,采用实例特征n 来估算该函数的空间复杂性。假定T 为int 类型,则数组a 中的每个元素需要2个字节,实参x需要2个字节,传值形式参数n 需要2个字节,局部变量i 需要2个字节,每个整型常量0和-1也分别需要2个字节。因此,所需要的总的数据空间为12字节。因为该空间独立于n,所以S顺序搜索(n)= 0。,顺序搜索的空间复杂性分析,10/23/2019,16,templateT Sum(T a,int n)/计算a0:n-1的和T tsum = 0;for(int i=0;i0) return Rsum(a,n-1)+an-1; return 0;,程序1-9 空间复杂性分析,10/2
7、3/2019,18,每一次调用Rsum 需要6个字节的栈空间。由于递归的深度为n+1,所以需要6(n+1)字节的递归栈空间,因而SRsum(n)=6(n+1)。,程序1-9 空间复杂性分析,10/23/2019,19,程序1-7计算n!的递归函数int Factorial(int n)/计算n!if(n=1) return 1;return n*Factorial(n-1);SFactorial(n)=?,阶乘 空间复杂性分析,10/23/2019,20,templateVoid Perm(T list,int k,int m)/生成listk:m的所有排列方式int i;if(k = m)/
8、输出一个排列方式for(i=0;i=m;i+)coutlisti;coutendl;else/listk:m有多个排列方式,递归地产生这些排列方式for(i=k;i=m;i+)Swap(listk,listi);Perm(list,k+1,m);Swap(listk,listi); SPerm (n) = ?,排列 空间复杂性分析,10/23/2019,21,template int SequentialSearch(T a, const T SP (n) = ?,执行顺序搜索的递归函数,10/23/2019,22,为了比较两个完成同一功能的程序的时间复杂性;为了预测随着实例特征的变化,程序运
9、行时间的变化量。,2.3 Time Complexity,10/23/2019,23,一个程序P所占用的时间T(P)=编译时间+运行时间。编译时间与实例的特征无关。因此将主要关注程序的运行时间。运行时间通常用“tp(实例特征)”来表示。,时间复杂性,10/23/2019,24,精确困难?找出一个或多个关键操作(对时间复杂性的影响最大),确定这些关键操作所需要的执行时间;确定程序总的执行步数。,估算运行时间方法,10/23/2019,25,求最大元素多项式求值(Polynomial evaluation)按名次排序(Rank sort)选择排序(Selection sort)冒泡排序(Bubbl
10、e sort)插入排序(Insertion sort)顺序搜索(Sequential search)名次排序优化/选择排序优化/冒泡排序优化,操作计数Operation Counts,10/23/2019,26,templateint Max(T a, int n)/ 寻找a 0 : n-1中的最大元素int pos = 0;for (int i = 1; i n; i+)if (apos ai)pos = i;return pos;每次调用Max(a,n)需要执行n-1次比较。,程序1-31 寻找最大元素,10/23/2019,27,多项式求值,10/23/2019,28,程序2-3多项式求
11、值算法,template T PolyEval(T coeff, int n, const T,10/23/2019,29,使用维数n 作为实例特征。假定根据for循环内部所执行的加和乘的次数来估算时间复杂性。进入for循环的总次数为n,每次循环执行1次加法和2次乘法(这种操作计数不包含循环控制变量i 每次递增所执行的加法)。加法的次数为n,乘法的次数为2n。,多项式求值算法时间复杂性,10/23/2019,30,多项式求值优化,Horner 法则采用如下的分解式计算一个多项式:P(x)=(cn*x+cn-1)*x+cn-2)*x+cn-3)*x+)*x+c0,10/23/2019,31,程序
12、2-4 利用Horner 法则对多项式进行求值,template T Horner(T coeff, int n, const T,10/23/2019,32,比较,可以估算出该程序的时间复杂性为n 次加法和n 次乘法。由于函数PolyEval 所执行的加法次数与Horner 相同,而乘法次数是Horner的两倍,因此,函数 Horner 应该更快。,10/23/2019,33,元素在队列中的名次(rank)可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。例如,给定一个数组a=4, 3, 9, 3, 7作为队列,则各元素的名次为r=2,0,4,1,3。,计算名次,10/
13、23/2019,34,template void Rank(T a, int n, int r) /计算a 0:n-1中n个元素的排名for (int i = 0; i n; i+)ri = 0; /初始化/逐对比较所有的元素for (int i = 1; i n; i+)for ( int j = 0; j i; j+)if (a j = a i) ri+;else rj +;,程序2-5 计算名次,10/23/2019,35,根据a的元素之间所进行的比较操作来估算程序的时间复杂性。对于i的每个取值,执行比较的次数为i,所以总的比较次数为1+2+3+ +n-1 = (n-1)n/2。,计算名
14、次时间复杂性,10/23/2019,36,程序2-6 利用附加数组重排数组元素template void Rearrange (T a, int n, int r) /按序重排数组a中的元素,使用附加数组uT *u = new Tn+1;/在u中移动到正确的位置for (int i = 0; i n; i+)uri = ai;/移回到a中for (int i = 0; i n; i+)ai = ui ;delete u;,名次排序Rank Sort/计数排序,10/23/2019,37,比较操作次数 = (n-1)n/2 移动操作次数 = 2n,名次排序Rank Sort性能,10/23/20
15、19,38,template void Rearrange (T * ,优化名次排序Rank Sort,10/23/2019,39,思想:首先找出最大的元素,把它移动到an-1,然后在余下的n-1个元素中寻找最大的元素并把它移动到an-2,如此进行下去。,选择排序 selection sort,10/23/2019,40,templateint Max(T a, int n)/ 寻找a 0 : n-1中的最大元素int pos = 0;for (int i = 1; i n; i+)if (apos 1; size- -) int j= Max(a, size); /size-1次比较Swap
16、( aj,asize-1 ) ; /移动3次,选择排序算法实现,10/23/2019,42,按照元素的比较次数来估算函数的时间复杂性。每次调用Max(a,size)需要执行size-1次比较,所以总的比较次数为1+2+3+n-1= (n-1)n/2。元素的移动次数为3(n-1)。比较操作次数 = (n-1)n/2 移动操作次数 = 3(n-1)与名次排序比较。,选择排序时间复杂性,10/23/2019,43,采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中,对相邻的元素进行比较,如果左边的元素大于右边的元素,则交换这两个元素。在一次冒泡过程结束后,可以确信最大的元素肯定在最右边的位置上。例
17、: 5 , 3 , 7 , 1 ,在第一次冒泡过程结束后,得到?,冒泡排序 bubble sort,10/23/2019,44,template void Bubble (T a, int n) /把数组a0:n-1中最大的元素通过冒泡移到右边for ( int i = 0; i ai+1) Swap(ai,ai+1);,程序2-8 一次冒泡,10/23/2019,45,template void BubbleSort (T a, int n)/对数组a0:n-1中的n个元素进行冒泡排序for ( int i = n; i1; i- -)Bubble(a,i) ;,冒泡排序,10/23/201
18、9,46,比较操作次数 = (n-1)n/2 移动操作次数 = 0 最好 = 3(n-1)n/2 最坏。名次排序和选择排序仅和n有关(最好=最坏)冒泡排序不但和n有关,还和实例具体值有关。(最好最坏),冒泡排序时间复杂性,10/23/2019,47,最好、最坏和平均操作数,10/23/2019,48,templateint SequentialSearch(T a, const T 假定每个元素被查找的概率是相同的 =?,顺序搜索成功查找的平均比较次数,10/23/2019,49,向有序数组a0:n-1中插入一个元素。a中的元素在执行插入之前和插入之后都是按递增顺序排列的。例如,向数组a0:5
19、 = 1,2,6,8,9,11中插入4,得到的结果为a0:6=1,2, 4,6,8,9,11。当为新元素找到欲插入的位置时,必须把该位置右边的所有元素分别向右移动一个位置。对于本例,需要移动11,9,8和6,并把4插入到新空出来的位置a2中。,向有序数组中插入元素,10/23/2019,50,templatevoid Insert(T a, int / 添加了一个元素 平均比较次数?,程序2-10 向一个有序数组中插入元素,10/23/2019,51,假定x 有相等的机会被插入到任一个可能的位置上(共有n + 1个可能的插入位置)。如果x 最终被插入到a的i+1处,i0,则执行的比较次数为n-
20、i。如果x 被插入到a0,则比较次数为n。所以平均比较次数为:,平均比较次数,10/23/2019,52,2-6名次排序的缺点?void Rearrange (T * ,优化名次排序,10/23/2019,53,从a0 开始,每次检查一个元素。如果当前正在检查的元素为ai 且ri= i,那么可以跳过该元素,继续检查下一个元素;如果rii, 可以把ai与ari 进行交换,交换的结果是把原ai 中的元素放到正确的排序位置(ri)上去。这种交换操作在位置i 处重复下去,直到应该排在位置i 处的元素被交换到位置i处。之后,继续检查下一个位置。,优化名次排序-原地重排,10/23/2019,54,程序2
21、 - 11 原地重排数组元素templatevoid Rearrange(T a, int n, int r)/ 原地重排数组元素for (int i = 0; i 1; size- -)int j= Max(a, size); Swap( aj,asize-1 ) ; ,优化选择排序,10/23/2019,57,程序2-7中选择排序函数的一个缺点是:即使元素已经按序排列,程序仍然继续运行。为了终止不必要的循环,在查找最大元素期间,可以顺便检查数组是否已按序排列。,优化选择排序,10/23/2019,58,templatevoid SelectionSort(T a, int n)/ 及时终止
22、的选择排序bool sorted = false;for(int size = n; !sorted 最坏情况下比较次数,移动次数 ? 最好情况下比较次数,移动次数 ?,程序2-12 及时终止的选择排序,10/23/2019,59,选择排序性能,最好情况:数组a有序。最坏情况:数组a最大元素在首位,其他与元素已经有序。 最好 最坏比较 n-1 n(n-1)/2移动 3 3(n-1),10/23/2019,60,2-9冒泡排序的缺点?void Bubble (T a, int n) for ( int i = 0; i ai+1) Swap(ai,ai+1);void BubbleSort (T
23、 a, int n)for ( int i = n; i1; i- -)Bubble(a,i) ;,优化冒泡排序,10/23/2019,61,如果在一次冒泡过程中没有发生元素互换,则说明数组已经按序排列,没有必要再继续进行冒泡过程。,优化冒泡排序,10/23/2019,62,templatebool Bubble(T a, int n) /把a0:n-1 中最大元素冒泡至右端bool swapped = false; / 尚未发生交换for (int i = 0; i ai+1) Swap(ai, ai+1);swapped = true; / 发生了交换return swapped;,程序2
24、-13 及时终止的冒泡排序,10/23/2019,63,templatevoid BubbleSort(T a, int n)/ 及时终止的冒泡排序for(int i = n;i1 最坏情况下比较次数,移动次数 ?最好情况下比较次数,移动次数 ?,程序2-13 及时终止的冒泡排序,10/23/2019,64,冒泡排序性能,最好情况:数组a最初已经有序。最坏情况:数组a倒序。 最好 最坏比较 n-1 n(n-1)/2移动 0 3*n(n-1)/2,10/23/2019,65,思想:因为只有一个元素的数组是一个有序数组,所以可以从包含n个元素的数组的第一个元素开始。通过把第二个元素插入到这个单元数
25、组中,可以得到一个大小为2的有序数组。插入第三个元素可以得到一个大小为3的有序数组。按照这种方法继续进行下去,最终将得到一个大小为n的有序数组。,插入排序Insertion Sort,10/23/2019,66,templatevoid Insert(T a, int n, const T,插入排序,10/23/2019,67,templatevoid InsertionSort(T a, int n)for (int i=1; i = 0 最坏情况下比较次数? 移动次数? 最好情况下比较次数? 移动次数?,程序2-15 另外一种插入排序,10/23/2019,68,插入排序性能,最好情况:数
26、组a最初已经有序。最坏情况:数组a倒序。 最好 最坏比较 n-1 n(n-1)/2移动 n-1 n-1+n(n-1)/2,10/23/2019,69,排序算法比较,算法 最好 最坏名次排序 比较n(n-1)/2+n n(n-1)/2+n 移动 0 6(n-1)选择排序 比较 n-1 n(n-1)/2 移动 3 3(n-1)冒泡排序 比较 n-1 n(n-1)/2 移动 0 3*n(n-1)/2插入排序比较 n-1 n(n-1)/2移动 n-1 n-1+n(n-1)/2,10/23/2019,70,利用操作计数方法来估算程序的时间复杂性忽略了所选择操作之外其他操作的开销。在统计执行步数的方法中,
27、要统计程序/函数中所有部分的时间开销。与操作计数一样,执行步数也是实例特征的函数。,执行步数Step Counts,10/23/2019,71,程序步可以定义为一个语法或语义意义上的程序片段,该片段的执行时间独立于实例特征。可以通过创建一个全局变量count 来确定一个程序或函数为完成其预定任务所需要的执行步数。把count 引入到程序语句之中,每当原始程序或函数中的一条语句被执行时,就为count 累加上该语句所需要的执行步数。当程序或函数运行结束时所得到的count的值即为所需要的执行步数。,程序步program step,10/23/2019,72,templateT Sum(T a,
28、int n)/ 计算a0:n - 1中元素之和T tsum=0;count+; / 对应于tsum=0for (int i=0; i 0)count+;/对应于return和Rsum 调用return Rsum(a,n-1)+an-1; count+; /对应于returnreturn 0; count=?,程序2-18 统计程序1-9的执行步数,10/23/2019,75,令tRsum(n)为程序Rsum结束时count所增加的值,可以看出tRsum(0)=2。当n0时,count所增加的值为2加上调用函数Rsum所增加的值。从tRsum(n)的定义可知,额外的增值为tRsum(n-1)。所
29、以,如果count的初值为0,在程序结束时它的值将变成2+tRsum(n-1),其中n0。,分析,10/23/2019,76,在分析一个递归程序的执行步数时,通常可以得到一个计算执行步数的递归等式(如tRsum(n)=2+tRsum(n-1),n0且tRsum(2)=0)。这种递归公式被称为递归等式(recurrence equation) 。可以采用重复迭代的方法来计算递归等式,如:tRsum(n)=2+tRsum(n-1)=2+2+tRsum(n-2)=4 +tRsum(n-2).=2n+tRsum(0)=2(n+1)其中n0,因此函数Rsum的执行步数为2(n+1)。,分析,10/23/
30、2019,77,比较程序Sum和程序RSum的执行步数,可以看到程序RSum的执行步数(2n+2)小于程序Sum的执行步数(2n+3)。不过不能因此断定程序Sum就比程序RSum慢,因为程序步不代表精确的时间单位。Rsum中的一步可能要比Sum中的一步花更多的时间,所以Rsum有可能要比Sum慢。,比较,10/23/2019,78,执行步数可用来帮助我们了解程序的执行时间是如何随着实例特征的变化而变化的。从Sum的执行步数中可以看到,如果n 被加倍,程序运行时间也将加倍(近似地);如果n增加10倍,运行时间也会增加10倍。所以可以预计,运行时间随着n 线性增长。称Sum是一个线性程序(其时间复
31、杂性与实例特征n 呈线性关系)。,执行步数,10/23/2019,79,如果不想使用count计值语句,可以建立一张表,在该表中列出每条语句所需要的执行步数。建立这张表时,可以首先确定每条语句每一次执行所需要的步数以及该语句总的执行次数(即频率),然后利用这两个量就可以得到每条语句总的执行步数,把所有语句的执行步数加在一起即可得到整个程序的执行步数。,执行步数表,10/23/2019,80,把存储在二维数组a0:rows-10:cols-1和b0:rows-10:cols-1中的两个矩阵相加。templatevoid Add(T *a,T *b,T *c,int rows,int cols)/
32、矩阵a和b相加得到矩阵c.for(int i=0;irows;i+)for(int j=0;jcols;j+)cij=aij+bij;,程序2-19矩阵加法,10/23/2019,81,templatevoid Add(T *a,T *b,T *c,int rows,int cols)/矩阵a和b相加得到矩阵c.for(int i=0;irows;i+)count+;/对应于上一条for语句for(int j=0;jcols,提高性能方案?,分析,10/23/2019,83,语句每次执行所需要的步数通常记为s/e,一条语句的s/e就等于执行该语句所产生的count值的变化量。,s/e,10/2
33、3/2019,84,一条语句的程序步数与该语句每次执行所需要的步数(s/e)之间有重要的区别,区别在于程序步数不能反映该语句的复杂程度。例如语句:x=Sum(a,m);的程序步数为1,而该语句的执行所导致的count值的实际变化为1加上调用Sum所导致的count值的变化(2m + 3)之和,因此该语句每次执行所需要的步数为1+2m+3=2m+4。,执行步数表,10/23/2019,85,10/23/2019,86,10/23/2019,87,10/23/2019,88,b是a的转置,当且仅当对于所有的i和j,有bij=aji,矩阵转置,10/23/2019,89,templatevoid T
34、ranspose(T *a,int rows)/对矩阵a0:rows-10:rows-1进行转置for(int i=0;irows;i+)for(int j=i+1;j0,则f(n)=O(nm)。,有用的结论,10/23/2019,105,加法规则,T(n)=T1(n)+T2(n) =O(g1(n) + O(g2(n) =O(max(g1(n),g2(n),10/23/2019,106,乘法规则,T(n)=T1(n)*T2(n) =O(g1(n) * O(g2(n) =O(g1(n)*g2(n),10/23/2019,107,void exam ( float x , int m, int n
35、 ) float sum ; for (int i=0;im;i+) /x中各行数据累加 sumi = 0.0; for (int j = 0; jn; j+) sumi += xij; for (i=0; im; i+) /打印各行数据和 cout i “ : ” sum i 3n,因此f(n)= (n)。对于所有的n0,有f(n)=10n2+4n+210n2,因此f(n)= (n2)。由于6*2n+n26*2n,所以6*2n+n2= (2n)。,例子,10/23/2019,111,g(n)仅是f(n)的一个下限。为了使语句f(n)= (g(n)更有实际意义,其中的g(n)应足够地大。因此常用的是3n+3=(n)及6*2n+n2= (2n),而不是3n+3=(1)及6*2n+n2= (1),尽管后者也是正确的。,Omega Notation,10/23/2019,112,定理2-3 如果f(n)=amnm+a1n+a0且am0,则f(n)= (nm)。,
限制150内