浏览 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 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2007-12-16
”我们知道“大O表示法把算法的效率分为四个级别:O(1),O(logN),O(N),O(N^2)。
头一次听说四个级别的划分法。。。 |
|
返回顶楼 | |
发表时间:2007-12-17
寒一个~~~~~
这三种排序都是n^2级别的 按照楼主的说法,所有的比较式排序都是中或以下 |
|
返回顶楼 | |