首先要说明一下,我们知道大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-15 22:40
- 浏览 1314
- 评论(2)
- 论坛回复 / 浏览 (2 / 2382)
- 查看更多
相关推荐
分析和计算算法效率的便捷方法 (杨朝霞兰州交通大学数理与软件工程学院,甘肃兰州 730070) : 摘 要: 通过对典型算法时间效率特征的分析,将求解算法时间复杂度的复杂过程进行简化,提出按算法的不同结构特性,具体问题...
算法设计与分析课件-第二章 算法效率分析基础 本章节主要介绍算法效率分析的基础知识,包括算法效率的定义、时间效率和空间效率的度量、分析框架、渐进符号和基本效率类型等。 一、算法效率的定义 一个问题往往有...
总的来说,这个课程设计是一个很好的实践平台,它让学习者亲身体验到算法效率的差异,并通过实际操作理解线性搜索和二叉搜索的优劣。通过比较不同N值下的运行时间,可以直观地看到算法效率随数据规模增长的变化趋势...
各种排序算法效率分析比较及源代码 C语言实现 各种排序包括: 直接插入排序,折半插入排序,2—路插入排序和表插入排序;希尔排序和链式基数排序;起泡排序,快速排序,归并排序;简单选择排序,树形选择排序和堆...
第四课:算法效率的度量和存储空间需求 第五课:线性表的类型定义 第六课:线性表的顺序表示和实现 第七课:实验一 线性表的顺序存储实验 第八课:线性表的链式表示与实现 第九课:循环链表与双向链表 第十课...
各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶,或大概执行时间。设计和实现内部排序算法效率比较平台,通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观的感受。
要求完成在正序、逆序、小规模数据量(10、30、50)和大规模数据量(100、1000、10000等)情况下以移动次数和比较次数来分析算法效率。 几种内部排序算法在进行时间复杂度分析的时候给出了算法执行的大概执行时间。...
【算法设计与实现-绪论与算法效率分析】 在计算机科学中,算法是解决问题的关键,它们是计算的灵魂,触及到科学、商业和技术的各个领域。算法设计与分析是一门核心课程,旨在帮助学习者理解如何有效地解决问题并...
搜索算法效率比较 在计算机科学与技术专业 kurs 设计中,搜索算法效率比较是一个非常重要的课题。本文将从设计报告的角度,介绍搜索算法效率比较的设计思路、设计内容、设计分析、设计实践和测试方法等方面的知识点...
"算法效率分析基础" 这篇 ppt 介绍了算法效率分析的基础知识,包括算法效率的度量、函数的渐进的界、算法的基本复杂性类型、算法复杂性分析的基本方法、非递归算法的复杂性分析、递归算法的复杂性分析、递归算法与...
"算法效率分析基础" 本章节讲解了算法效率分析的基础知识,涵盖了问题的规模、基本操作、计算复杂度、复杂度的量级、上下界等概念,并对循环算法与递归算法的复杂度分析方法进行了介绍。 一、问题的规模 算法效率...
搜索算法效率比较 搜索算法效率比较是计算机科学与技术专业的设计课程报告,旨在比较不同的搜索算法的效率。该报告从设计题目、设计目的及要求、设计内容、设计分析、设计实践、测试方法等方面对搜索算法效率进行了...
老师的课件,比较好懂容易,只花费1个资源分
本文针对目前提出的匹配算法效率分析方法存在的匹配次数差异大、分析内存占用率高的问题,基于大数据处理技术,提出了一种新的模式匹配算法效率分析方法,并通过实验验证了该方法的有效性。 首先,文章指出现有的...
算法效率分析基础 算法效率分析是对一个算法需要多少计算时间和存储空间作定量的分析。时间是非常重要的,不是所有能计算的都有价值,不是所有有价值的都能被计算。这章节将介绍算法效率分析的基础知识,包括算法...
在计算机科学中,算法效率分析是评估算法性能的关键手段。本讲义主要探讨了如何评价算法的效率,包括时间效率和空间效率,并介绍了相关概念和分析框架。 首先,评价一个算法要考虑以下几个方面:正确性(算法是否能...
《排序算法效率分析——动态显示排序过程》 在信息技术领域,排序算法是计算机科学的基础,其性能直接影响到程序的运行效率。本软件是由资深算法研究者精心编写的,旨在通过动态展示排序算法的过程,帮助用户深入...
【算法效率】是计算机科学中的核心概念,它关乎到程序执行的效率和资源消耗。算法是解决问题的具体步骤集合,可以通过自然语言、程序设计语言、类程序设计语言或流程图等多种方式来描述。一个有效的算法必须具备五个...