算法设计：第三讲——2013

《算法设计：第三讲——2013》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、直接计算法：循环的次数与问题规模n直接或间接相关。与问题规模n直接相关x=0;y=0;for(k=1;k<=n;k++)x=x+1;for(i=1;i<=n;i++)for(j=1;j<=n;j++)y=y+1;非递归算法的时间复杂度分析方法统计嵌套层数最多的语句的频度。循环次数间接依赖规模nx=1;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;非递归算法的时间复杂度分析方法执行次数：[n(n+1)(2n+1)/6+n(n+1)/2]/2时间复杂度：O(n3)循环次数间接依赖规模n相关例题：（1）冒泡排序：

2、内循环线性递减（2）选手的竞技淘汰比赛：内循环呈n/2k递减（k=1,2,…log2n）——几何级数（3）洗牌程序：内循环呈n/k递减（k=1,2,…,n)——调合级数非递归算法的时间复杂度分析总结直接计算法：使用循环次数已知的情况。迂回计算法：循环结构中循环次数与循环体内语句的执行有联系。先设循环次数为k根据循环结束的条件求出k计算算法复杂度的阶迂回计算法例1：算法voidfun1(intn){inti=1,s=100;while(i

3、s+i;}}迂回计算法例3：算法voidfun2(intn){inti=0,j;do{for(j=0;j

4、,r，0≤p≤q≤r＜m，使得A[p]～A[q]和A[q+1]～A[r]分别是两个以递增顺序排序的子数组。把这两个子数组按递增顺序合并在A[p]～A[r]中。算法设计基本操作频率的统计分析该算法中的比较次数：令数组1的长度为n1，数组2的长度为n2，其中n1+n2=n在进行排序时，比较的次数最少：n1次最多：n-1次基本操作频率的统计因此，如果合并两个大小接近的有序数组，例如这时，可以选取数组元素的比较操作作为算法的基本操作。因为此时数组元素的比较操作，和所有其他初等操作的最高执行频率，相差在一个常数因子之内。这时，算法的时间复杂性仍然是Θ(n)。基本操作频率的统计很多问题

5、，都可以选择一个基本操作，通过寻找这个基本操作的阶，而得出算法运行时间的阶。基本操作的选择，通常检索和排序：元素比较操作遍历链表：设置或更新链表指针图的遍历：访问图中顶点基本操作频率的统计在大部分情况下，算法的执行时间不仅与问题的规模有关，而且与输入的实例有关。根据输入实例的不同，又把算法的时间复杂性分为最好情况分析平均情况分析最坏情况分析时间复杂度的分析例：用插入法对n个元素的数组A，按递增顺序进行排序。算法设计（1）最好情况分析：（2）最坏情况分析：时间复杂度的分析进行n-1次比较最好情况与最坏情况分析寻找该算法的极端实例，然后分析在该极端实例下算法的运行时间。例1：线

6、性检索法：在n个元素的数组中，用线性检索方法检索元素x。例2：二叉检索算法：在具有n个已排序过的元素的数组中，二叉检索方法检索元素x。时间复杂度的分析平均情况分析：算法的运行时间取算法所有可能输入的平均时间。必须知道所有输入出现的概率，即所有输入的分布情况。在一般情况下，假定输入是平均分布的（等概率）。时间复杂度的分析例1：插入排序算法的平均情况分析。假定数组A中的元素为：并且：（1）插入排序算法中元素比较次数，取决于数组中元素的初始排列顺序。n个元素共有n!种排列，假定每一种排列的概率相同。时间复杂度的分析(2)插入元素xi的平均比较次数时间复杂度的分析(3)平均比较总次

7、数时间复杂度的分析例2：改进的冒泡算法改进的算法（1）最好情况：外循环1次，内循环n-1次（2）最坏情况：时间复杂度的分析（3）平均比较次数逆序：设是集合的一个排列，如果且，则对偶称为该排列的一个逆序。时间复杂度的分析例如，排列3，4，1，5有两个逆序:（3,1)(4,1)如果希望使上面的元素按序排列，则上面的元素至少必须交换两次。交换不满足排序要求的两个相邻元素，则逆序的总数将减1。冒泡排序就是不断地交换一个排列的两个相邻元素，使其逆序个数往减少的方向改变，当逆序个数减少为0时，排序结束。时间复杂度的分析逆序的平