基于二分排序法时间复杂度的求解过程

饶正婵，范林柏

（ 1.铜仁学院 计算机科学系，贵州 铜仁 554300；

2.湖南大学 软件学院，湖南 长沙 410006）

基于二分排序法时间复杂度的求解过程

饶正婵1,2，范林柏2

（ 1.铜仁学院 计算机科学系，贵州 铜仁 554300；

2.湖南大学 软件学院，湖南 长沙 410006）

对算法设计的效果进行全面分析是每一个软件项目管理中具体算法设计时所要考虑的问题之一。对算法作时间及空间复杂度的度量，是一项重要的工作。对二分查找排序法的时间复杂度的求解过程进行全面分析，得到时间复杂度的求解方法，这对于掌握算法的设计有大的帮助。

算法； 时间复杂度； 二分查找； 度量

1.引言

同一问题可用不同算法解决，而算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于针对问题选择合适的算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑[1]。一些算法是高效的，而另一些算法却是低效的，那么怎样评价一个算法的好与坏呢？一些问题容易解决，而另一些却不易解决，那么怎样评价一个问题的难易程序呢？这些问题是作为计算机软件开发人员在设计算法的过程中必须要考虑的问题。怎样对一些经典算法的性能进行有效的度量，该度量又是以什么为依据而获得的，都是需要考虑的问题。下面针对二分查找排序法时间复杂度的求解过程进行讨论。

2.算法的度量

算法分析的目的在于选择合适算法和改进算法。一个算法的优劣用什么方法来进行有效评价呢？一般来讲，主要从时间复杂度和空间复杂度来考虑，这里先来简单分析时间复杂度和空间复杂度的概念。

一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。广义上讲时间复杂度[2]是指某算法的运行时间与问题规模的对应关系。

时间复杂度用T（n ）=O（f（n ））来表示，其中O表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，如果一个没有循环的代码，算法的执行频度是不会变的，记作O（1）。当算法中有一个单重循环，那执行频率就会呈线性增长O（n*n ）等等。

例如：

空间复杂度是指某一算法在运行过程中临时占用存储空间的大小。

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同配置的计算机上执行所花的时间会不一样，在不同时刻也会由于计算机资源竞争及占用情况的不同，使得算法在同一台计算机上的执行时间也不一样。

3.二分查找排序法时间复杂度分析

前面简单介绍了算法优劣的度量方法，这里针对经典的查找算法——二分查找法来分析其时间复杂度。在将一个数据集排序为递增或递减有序后，二分查找从序列的中间开始。如果查找的数据等于序列中间位置的数据，那么查找终止；否则，依据查找数据与中间位置数据比较的结果，可以递归地查找序列的左半部分或者右半部分。

3.1. 算法描述

用JAVA对二分查找排序法描述算法如下。

3.1. 时间复杂度求解

对于二分法排序最好情况下的分析是比较简单的，即只需一步就可以完成。

最坏情况下的分析也是相当简单的，很容易看出来最多需要 （[log2n]+1）步数就能完成二分查找排序[3][4]。

下面作具体讨论，这里为了简化假设=2k−1 n。

4.结论

对于一个给定的算法，我们要做两项分析：一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等；二是在已证明算法是正确的基础上分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级[5]，在很大程度上能很好地反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。

[1] 傅清祥，王晓东.算法与数据结构[M].北京：电子工业出版社，1998.

[2] 佚名.C#数据结构与算法系列（一） 基本概念[EB/OL].http：//www.cnblogs.com/whtydn/archive/2009/07/08/1519485.html，2009-07-08.

[3] 王卫东.算法设计与分析导论[M].北京：机械工业出版社，2007.

[4] 刘少辉，盛秋戬，史忠植.一种新的快速计算正区域的方法[J].计算机研究与发展，2003，（5）.

[5] 赵军，王国胤，吴中福，唐宏.一种高效的属性核计算方法[J].小型微型计算机系统，2003，（11）.

The Solution Process of Time Complexity Based on Dichotomy Sorting Method

RAO Zheng-chan1,2, FAN Lin-bai2
（ 1. Department of Mathematics and Computer Science, Tongren University, Tongren, Guizhou 554300, China;
2.Software School, Hunan University, Changsha, Hunan 410006, China ）

The comprehensive analysis of algorithm design effect is one of the problems to be considered in each project management. The measurement about time and space complexity of algorithm is an important task. This paper comprehensively analyzes the solution process of time complexity based on dichotomy sorting method and obtains its solution. It is a big help for the grasp of algorithm design.

algorithm;time complexity;binary search;measurement

（责任编辑 王婷婷）

TP311.53 < class="emphasis_bold">文献标识码：A

A

1673-9639 （2011） 03-0139-03

2010-05-08

饶正婵（1976-），女，侗族，贵州石阡人，讲师，湖南大学软件学院在读硕士，铜仁学院计算机教师，研究方向：现代教育技术、IT项目管理。