基于二分排序法時(shí)間復(fù)雜度的求解過(guò)程

饒正嬋，范林柏

（ 1.銅仁學(xué)院 計(jì)算機(jī)科學(xué)系，貴州 銅仁 554300；

2.湖南大學(xué) 軟件學(xué)院，湖南 長(zhǎng)沙 410006）

基于二分排序法時(shí)間復(fù)雜度的求解過(guò)程

饒正嬋1,2，范林柏2

（ 1.銅仁學(xué)院 計(jì)算機(jī)科學(xué)系，貴州 銅仁 554300；

2.湖南大學(xué) 軟件學(xué)院，湖南 長(zhǎng)沙 410006）

對(duì)算法設(shè)計(jì)的效果進(jìn)行全面分析是每一個(gè)軟件項(xiàng)目管理中具體算法設(shè)計(jì)時(shí)所要考慮的問(wèn)題之一。對(duì)算法作時(shí)間及空間復(fù)雜度的度量，是一項(xiàng)重要的工作。對(duì)二分查找排序法的時(shí)間復(fù)雜度的求解過(guò)程進(jìn)行全面分析，得到時(shí)間復(fù)雜度的求解方法，這對(duì)于掌握算法的設(shè)計(jì)有大的幫助。

算法； 時(shí)間復(fù)雜度； 二分查找； 度量

1.引言

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

2.算法的度量

算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的優(yōu)劣用什么方法來(lái)進(jìn)行有效評(píng)價(jià)呢？一般來(lái)講，主要從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮，這里先來(lái)簡(jiǎn)單分析時(shí)間復(fù)雜度和空間復(fù)雜度的概念。

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

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

例如：

空間復(fù)雜度是指某一算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間的大小。

一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量，算法執(zhí)行時(shí)間的度量不是采用算法執(zhí)行的絕對(duì)時(shí)間來(lái)計(jì)算的，因?yàn)橐粋€(gè)算法在不同配置的計(jì)算機(jī)上執(zhí)行所花的時(shí)間會(huì)不一樣，在不同時(shí)刻也會(huì)由于計(jì)算機(jī)資源競(jìng)爭(zhēng)及占用情況的不同，使得算法在同一臺(tái)計(jì)算機(jī)上的執(zhí)行時(shí)間也不一樣。

3.二分查找排序法時(shí)間復(fù)雜度分析

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

3.1. 算法描述

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

3.1. 時(shí)間復(fù)雜度求解

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

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

下面作具體討論，這里為了簡(jiǎn)化假設(shè)=2k?1 n。

4.結(jié)論

對(duì)于一個(gè)給定的算法，我們要做兩項(xiàng)分析：一是從數(shù)學(xué)上證明算法的正確性，這一步主要用到形式化證明的方法及相關(guān)推理模式，如循環(huán)不變式、數(shù)學(xué)歸納法等；二是在已證明算法是正確的基礎(chǔ)上分析算法的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)[5]，在很大程度上能很好地反映出算法的優(yōu)劣與否。因此，作為程序員，掌握基本的算法時(shí)間復(fù)雜度分析方法是很有必要的。算法時(shí)間復(fù)雜度分析是一個(gè)很重要的問(wèn)題，任何一個(gè)程序員都應(yīng)該熟練掌握其概念和基本方法，而且要善于從數(shù)學(xué)層面上探尋其本質(zhì)，才能準(zhǔn)確理解其內(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)東.算法設(shè)計(jì)與分析導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2007.

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

[5] 趙軍，王國(guó)胤，吳中福，唐宏.一種高效的屬性核計(jì)算方法[J].小型微型計(jì)算機(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

（責(zé)任編輯 王婷婷）

TP311.53 < class="emphasis_bold">文獻(xiàn)標(biāo)識(shí)碼：A

A

1673-9639 （2011） 03-0139-03

2010-05-08

饒正嬋（1976-），女，侗族，貴州石阡人，講師，湖南大學(xué)軟件學(xué)院在讀碩士，銅仁學(xué)院計(jì)算機(jī)教師，研究方向：現(xiàn)代教育技術(shù)、IT項(xiàng)目管理。