排序算法时间复杂度的实验统计分析

2022-09-10

1 算法时间复杂度

按照文献[1]中的定义, 算法是一系列解决问题的指令。对于符合规定的输入, 算法要在有限的时间内得出所需要的输出。我们知道, 同一问题有不同的解决办法, 即存在多种算法, 每种算法所需要的资源 (主要是存储空间) 不同, 所消耗的时间也不同。评估一个算法的优劣主要从两个指标来进行, 一是该算法所占的资源 (主要指计算机内存) 多少, 另一个指标为在特定硬件和操作系统环境下所消耗的时间。二者之间经常可以进行某种折中, 如对某一特定问题, 存在两种算法, 算法1比算法2消耗的时间少, 但可能需要比算法2更多地内存空间。因此算法设计中经常有用时间换空间或反过来用空间换时间的方法。如何选择某一算法, 需要根据具体的项目对实时响应的要求及相应的硬件条件来决定。在计算机硬件快速发展的今天, 算法对硬件资源要求基本能得到满足。因此研究和评估一个算法的优劣主要是考虑所消耗的时间, 也就是需要对算法时间复杂度进行统计分析。

时间复杂度指标即算法所消耗的时间T (n) 可表示如下。

其中:C为常数, 表示在某台计算机及某个操作系统 (包括虚拟机) 下, 执行一个基本操作所需要的时间;E (n) 为算法需要的基本操作次数;n为问题的规模。

算法时间复杂度的实验方法就是通过实际排序程序的实现来统计计算所需要的时间, 并在此基础上进行分析, 得出有关各类算法的评估结果。

2 排序算法伪代码描述

常用的排序算法有:冒泡算法、选择算法、插入算法、归并算法、快速算法。关于各种算法的具体实现方法可参见[1], 本文不详细描述, 以下给出各种算法的伪代码表示法。

2.1 冒泡排序算法的伪代码描述如下

2.2 选择排序算法的伪代码描述如下

2.3 插入算法的伪代码描述如下

2.4 归并算法的伪代码描述如下

合并过程的Merge函数实现方法参见[1]。

2.5 快速算法的伪代码描述如下

3 排序算法时间复杂度实验分析软件

为了研究和比较各种算法的时间复杂度, 就必须要编写各类算法的实现程序, 同时对给定的序列数进行排序实现, 然后, 统计每种算法的执行时间。为此需要开发一个应用软件, 该软件的主要功能如下。

(1) 实现上述5种排序算法。

(2) 给定长度分别为100000, 200000, , 400000, 800000的序列随机数, 调用各种排序算法进行排序, 并统计和显示所占用的时间。

(3) 分析每种算法所消耗的时间与给定序列数据长度的关系。

(4) 分析在给定同一长度的序列数据条件下, 分析各类算法所消耗的时间, 评估各类算法的效率。

可以在Vs2003.NET下用C#语言编写程序实现上述功能, 序列数据的定义采用数组方式。为了统计排序执行时间, 只需在调用排序算法的前后分别调用系统的时间, 两者相减即可。软件运行的界面如图1所示。

4 统计结果及分析

通过运行所编写的软件, 可以得出各类算法对应不同长度的序列数据进行排序所占用的时间, 表1所显示的为统计结果。如果多运行几次排序程序, 将所统计的时间进行平均, 可以得到更有代表性的统计数据。 (注:执行时间单位为毫秒)

分析上述表格中所显示的数据我们可以得出以下结论。

(1) 5种排序算法可以分为2大类, 冒泡排序、选择排序、插入排序为第一类, 归并排序、快速排序属于第2类。

(2) 第一类算法的排序执行时间与长度成平方关系, 即当长度扩展到2倍时, 对应的执行时间扩展到4倍。这个结论与[1]中的近似理论分析是相吻合的。

(3) 第二类算法执行时间在长度为400000到800000范围内, 几乎成线性规律增长, 由于这两类算法的精确的理论分析无法做到, 文献[1]给出了一个近似统计模型。

(4) 第2类算法效率明显要高于第1类算法。

(5) 第1类算法中, 插入排序算法效率最高, 冒泡排序算法效率最低。

(6) 第2类算法中。当长度n较小时, 快速排序算法效率要略高些, 当长度n较大时, 归并排序算法效率要略高些。

5 结语

排序算法在各类应用软件中都要用到, 其排序效率是软件开发人员需要重点考虑的问题。各类算法执行效率还与需要排序的数据本身特点有关系, 实际项目中如何选择, 还需要考虑其他因素, 如算法需要占用的空间等因素。本文介绍了用实验统计方法研究各类排序算法的时间复杂度问题, 得出的有关结论可供软件开发人员在实际项目中选择排序算法时参考。

摘要：本文叙述了各种排序算法的伪代码表示方法, 并针对各种排序算法, 描述如何利用实验方法进行算法时间复杂度的统计计算, 在此基础上, 叙述如何开发一个应用软件来对各种算法的时间复杂度进行横向和纵向比较分析, 得出各类算法的评估结论。统计分析的结果可直接应用于软件的设计和编码中。

关键词：排序,算法,时间复杂度