论坛首页 入门技术论坛

算法的效率

浏览 2382 次
锁定老帖子 主题:算法的效率
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2007-12-15  

首先要说明一下,我们知道大O表示法把算法的效率分为四个级别:O(1),O(logN),O(N),O(N^2),分别对应优,良,中,差。
接下来我对三种排序算法做了测试(运行环境:JDK6.0,windows XP命令提示符下执行,AMD 速龙3800+ 2.0GHz,内存512MB DDRII 667两条,双通道。):

1、先是给一组数组随机赋值,然后把这个数组再复制出两个,分别用三种排序算法为这三组一样的数组进行排序。数组长度为1万,测得排序时间:

冒泡排序消耗时间:0.453

选择排序消耗时间:0.187

插入排序消耗时间:0.062

2、上面测试的结果中差距不是很大吧,那么把这三个数组扩大10倍,长度加到10万,我们看看结果:

冒泡排序消耗时间:49.109

选择排序消耗时间:21.781

插入排序消耗时间:9.016

这下消耗的时间差很多了。

3、测试最理想情况下(数组已经是升序排序了),各算法的消耗时间(此时各数组长度为1万):

冒泡排序消耗时间:0.187

选择排序消耗时间:0.218

插入排序消耗时间:0.0

选择排序消耗的时间居然比冒泡排序法多!!插入排序法几乎不需要时间!这是为什么呢??

原来在冒泡排序法中,最理想的情况下比较的效率为O(N^2),选择排序法也一样,而插入排序法只需要比较n-1次,也就是说它的效率是O(N)级别的。理想情况下冒泡排序法的交换次数是0。而选择排序法虽然没有交换数据,但每次都对临时变量赋值消耗了时间,所以在最理想情况下,它的效率反而比冒泡低了。插入排序法的情况和选择排序法一样,需要每次比较时进行赋值,但最理想情况下,它的比较次数本来就少,是O(N)级别的,它在比较次数上省下来的资源完全足够用来运行O(N)赋值操作。这样一分析,运行结果就可以解释了。

4、最糟糕情况下(数组已经是降序排序好了的,我们需要把它反过来用升序排序),各算法的消耗时间(此时各数组长度为1万):

可以先猜测一下结果:冒泡排序消耗时间最多,选择排序和插入排序消耗时间差不多。
运行一下看看:
冒泡排序消耗时间:0.422

选择排序消耗时间:0.172

插入排序消耗时间:0.172
   发表时间:2007-12-16  
”我们知道“大O表示法把算法的效率分为四个级别:O(1),O(logN),O(N),O(N^2)。

头一次听说四个级别的划分法。。。
0 请登录后投票
   发表时间:2007-12-17  
寒一个~~~~~

这三种排序都是n^2级别的

按照楼主的说法,所有的比较式排序都是中或以下
0 请登录后投票
论坛首页 入门技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics