您当前位置:设计在线网 >> 自动控制理论 >> 浏览文章

如何选择排序时间复杂度分析

分享到:
本文章讲述了如何选择排序时间复杂度分析.

选择排

序时间复杂度分析 

 void selection_sort(void)

int i,j,min,temp;

for(i=0;i LEN;i++){

for(j=min=i;j LEN;j++)

if(a[min]a[j])

min=j;c1 temp=a[min];c2 a[min]=a[i];c3 a[i]=temp;c4

首先分析最坏情况:设n=LEN,m为内层循环执行次数。可得:总的执行时间=(n-1)*(c2+c3+c4)+m*c1(1)然后我们把m写成n的函数:根据经验,可得:m=n(n+1)/2代入(1)中,一眼就可以看出来可以表示成an^2+bn+c的形式(注意n(n+1)算出来本身就已经出现二次项了),是n的二次函数。所以最坏情况下选择排序的时间复杂度为Θ(n^2)。同理,平均情况下选择排序的时间复杂度为Θ(n^2)。最好情况:序列已经排好序。

但外层和内层循环还是会执行,所以最好情况下选择排序的时间复杂度依然为Θ(n^2)。可以看出,选择排序分不出最坏、平均、最好情况,它的时间复杂度是固定的。所以选择排序的时间复杂度为O(n^2)。本人初学算法时间复杂度分析,不保证100%正确,所以不要太相信我--!有错误麻烦请指正,谢谢。

推荐阅读:
如何运用遗传算法进行股票短期组合投资决策
有关电炉功率分布原理说明及分析
有关二维平面任意三点按逆时针排序算法总结
上一篇:介绍标准程序流程图的符号及使用约定
下一篇:没有了
推荐文章  
赞助商链接  
热门排行  
主题推广  
中国设计在线网 All Rights Reserved. 互联网违法和不良信息举报
信息产业部备案号:湘ICP备09001063号