《算法设计技巧与分析》第1章 算法分析的基本概念-教学课件（非AI生成）.ppt

1.12.2平均情况分析LINEARSEARCH算法中元素的比较次数在1~n之间,有n中可能性,每种可能性发生的概率为1/n在平均情况下，元素比较次数为故平均情况下的时间复杂度为?(n)。本章小结掌握算法的基本概念和具有的特征掌握渐进符号的含义重点掌握时间复杂度的概念,能够使用渐进符号表示掌握空间复杂度能够分析算法的时间复杂度和空间复杂度Exercises1.131.141.151.38AnexampleA[1..11]=6,10,9,5,3,11,4,8,1,2,76109531148127ikj……算法分析Observation1.3:选择排序算法的元素比较次数为n(n-1)/2.元素赋值的次数介于0和3(n-1)之间.1.6插入排序基本思想:从只包含一个元素的字数组A[1]开始接着,将元素A[2]插入到字数组A[1]的合适的位置,这个位置可能在A[1]之前或者A[1]之后,那么A[1..2]变为有序的字数组然后,插入A[3],A[4],直到所有的元素都插入,整个数组变为有序.Algorithm1.5INSERTIONSORTInput:AnarrayA[1..n]ofnelements.Output:A[1..n]sortedinnondecreasingorder.1.fori?2ton2.x?A[i]3.j?i-14.while(j0)and(A[j]x)5.A[j+1]?A[j]6.j?j-17.endwhile8.A[j+1]=x9.endforAnexampleA[1..11]=6,10,9,5,3,11,4,8,1,2,76109531148127ix=10j99……算法分析Observation1.4:插入排序的元素比较次数介于n-1和n(n-1)/2之间.元素赋值次数等于元素比较次数加上n-1.1.4合并两个有序的数组问题描叙假设我们有一个数组A[1…m]和三个下标p,q和r,其中1?p?qr?m.该数组的两个子部分A[p…q]和A[q+1…r]都是非递减排序.我们需要重新调整A中的元素,使得A[p…r]中的元素非递减排序.例子合并两个子数组2,3,66and7,11,13,45,57.2366711134557stk2371113455766end!Algorithm1.3MERGEInput:数组A[1…m]和三个下标p,q和r,其中1?p?qr?m.该数组的两个子部分A[p…q]和A[q+1…r]都是非递减排序Output:A[p…r]中的元素非递减排序.1.comment:B[p…r]是一个辅助数组2.s?p;t?q+1;k?p3.whiles?qandt?r4.ifA[s]?A[t]then5.B[k]?A[s];s?s+16.elseB[k]?A[t];t?t+17.endif8.k?k+19.endwhile10.ifs=q+1thenB[k…r]?A[t…r]11.elseB[k…r]?A[s…q]12.endif13.A[p…r]?B[p…r]算法分析Observation1.1:对于合并长度为n1和n2的两个数组(n1?n2,n=n1+n2),merge算法的元素比较次数介于n1和n-1之间.特别的是,如果两个数组的大小为?n/2?,元素比较次数介于?n/2?和n-1之间.Observation1.2:元素赋值次数为2n.1.7从底向上合并排序基本思想直接在数组上进行操作,利用两个有序数组合并的算法初始化变量,s=1,每一次循环s=2*si+1,i+s和i+t定义两个需要合并的子序列的边界.