饒正嬋，范林柏

（ 1.銅仁學院 計算機科學系，貴州 銅仁 554300；

2.湖南大學 軟件學院，湖南 長沙 410006）

基于二分排序法時間復雜度的求解過程

饒正嬋1,2，范林柏2

（ 1.銅仁學院 計算機科學系，貴州 銅仁 554300；

2.湖南大學 軟件學院，湖南 長沙 410006）

對算法設計的效果進行全面分析是每一個軟件項目管理中具體算法設計時所要考慮的問題之一。對算法作時間及空間復雜度的度量，是一項重要的工作。對二分查找排序法的時間復雜度的求解過程進行全面分析，得到時間復雜度的求解方法，這對于掌握算法的設計有大的幫助。

算法； 時間復雜度； 二分查找； 度量

1.引言

同一問題可用不同算法解決，而算法的優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于針對問題選擇合適的算法和改進算法。一個算法的評價主要從時間復雜度和空間復雜度來考慮[1]。一些算法是高效的，而另一些算法卻是低效的，那么怎樣評價一個算法的好與壞呢？一些問題容易解決，而另一些卻不易解決，那么怎樣評價一個問題的難易程序呢？這些問題是作為計算機軟件開發(fā)人員在設計算法的過程中必須要考慮的問題。怎樣對一些經(jīng)典算法的性能進行有效的度量，該度量又是以什么為依據(jù)而獲得的，都是需要考慮的問題。下面針對二分查找排序法時間復雜度的求解過程進行討論。

2.算法的度量

算法分析的目的在于選擇合適算法和改進算法。一個算法的優(yōu)劣用什么方法來進行有效評價呢？一般來講，主要從時間復雜度和空間復雜度來考慮，這里先來簡單分析時間復雜度和空間復雜度的概念。

一個程序的時間復雜度是指程序運行從開始到結(jié)束所需要的時間。廣義上講時間復雜度[2]是指某算法的運行時間與問題規(guī)模的對應關(guān)系。

時間復雜度用T（n ）=O（f（n ））來表示，其中O表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同，如果一個沒有循環(huán)的代碼，算法的執(zhí)行頻度是不會變的，記作O（1）。當算法中有一個單重循環(huán)，那執(zhí)行頻率就會呈線性增長O（n*n ）等等。

例如：

空間復雜度是指某一算法在運行過程中臨時占用存儲空間的大小。

一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量，算法執(zhí)行時間的度量不是采用算法執(zhí)行的絕對時間來計算的，因為一個算法在不同配置的計算機上執(zhí)行所花的時間會不一樣，在不同時刻也會由于計算機資源競爭及占用情況的不同，使得算法在同一臺計算機上的執(zhí)行時間也不一樣。

3.二分查找排序法時間復雜度分析

前面簡單介紹了算法優(yōu)劣的度量方法，這里針對經(jīng)典的查找算法——二分查找法來分析其時間復雜度。在將一個數(shù)據(jù)集排序為遞增或遞減有序后，二分查找從序列的中間開始。如果查找的數(shù)據(jù)等于序列中間位置的數(shù)據(jù)，那么查找終止；否則，依據(jù)查找數(shù)據(jù)與中間位置數(shù)據(jù)比較的結(jié)果，可以遞歸地查找序列的左半部分或者右半部分。

3.1. 算法描述

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

3.1. 時間復雜度求解

對于二分法排序最好情況下的分析是比較簡單的，即只需一步就可以完成。

最壞情況下的分析也是相當簡單的，很容易看出來最多需要 （[log2n]+1）步數(shù)就能完成二分查找排序[3][4]。

下面作具體討論，這里為了簡化假設=2k?1 n。

4.結(jié)論

對于一個給定的算法，我們要做兩項分析：一是從數(shù)學上證明算法的正確性，這一步主要用到形式化證明的方法及相關(guān)推理模式，如循環(huán)不變式、數(shù)學歸納法等；二是在已證明算法是正確的基礎上分析算法的時間復雜度。算法的時間復雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級[5]，在很大程度上能很好地反映出算法的優(yōu)劣與否。因此，作為程序員，掌握基本的算法時間復雜度分析方法是很有必要的。算法時間復雜度分析是一個很重要的問題，任何一個程序員都應該熟練掌握其概念和基本方法，而且要善于從數(shù)學層面上探尋其本質(zhì)，才能準確理解其內(nèi)涵。

[1] 傅清祥，王曉東.算法與數(shù)據(jù)結(jié)構(gòu)[M].北京：電子工業(yè)出版社，1998.

[2] 佚名.C#數(shù)據(jù)結(jié)構(gòu)與算法系列（一） 基本概念[EB/OL].http：//www.cnblogs.com/whtydn/archive/2009/07/08/1519485.html，2009-07-08.

[3] 王衛(wèi)東.算法設計與分析導論[M].北京：機械工業(yè)出版社，2007.

[4] 劉少輝，盛秋戩，史忠植.一種新的快速計算正區(qū)域的方法[J].計算機研究與發(fā)展，2003，（5）.

[5] 趙軍，王國胤，吳中福，唐宏.一種高效的屬性核計算方法[J].小型微型計算機系統(tǒng)，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-），女，侗族，貴州石阡人，講師，湖南大學軟件學院在讀碩士，銅仁學院計算機教師，研究方向：現(xiàn)代教育技術(shù)、IT項目管理。