摘要：算法設(shè)計(jì)與算法時(shí)間復(fù)雜度分析是數(shù)據(jù)結(jié)構(gòu)中研究算法的重要內(nèi)容。本文主要介紹如何針對實(shí)際問題設(shè)計(jì)效率較高的算法以及對算法的時(shí)間復(fù)雜度進(jìn)行分析的方法。

關(guān)鍵詞：算法；算法設(shè)計(jì)；時(shí)間復(fù)雜度

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)14-20878-03

1 算法的定義與特性

算法是一個(gè)有窮的指令集，這些指令是為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。一般應(yīng)具有如下特性：(1)輸入：應(yīng)有0個(gè)或多個(gè)輸入；(2)輸出：有一個(gè)或多個(gè)結(jié)果輸出；(3)確定性：每一步定義都是確切的、無歧義的；(4)有窮性：算法應(yīng)在執(zhí)行有窮步后結(jié)束；5)有效性：每一條運(yùn)算應(yīng)足夠基本。

2 算法的描述

算法的描述方法一般有：語言方式、圖形方式、表格方式等。

算法的描述原則：自頂向下、逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。

下面以直接選擇排序說明算法描述過程。

選擇排序的基本思想是：每一趟（例如第i趟，i = 0，1，…，n-2）在后面n-i個(gè)待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象， 作為有序?qū)ο笮蛄械牡趇個(gè)對象。待到第n-2趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。

基本步驟是：

在一組對象a[i]～a[n-1]中選擇具有最小關(guān)鍵碼的對象；若它不是這組對象中的第一個(gè)對象，則將它與這組對象中的第一個(gè)對象對調(diào)；

在這組對象中剔除這個(gè)具有最小關(guān)鍵碼的對象，在剩下的對象a[i+1]～a[n-1]中重復(fù)執(zhí)行，直到剩余對象只有一個(gè)為止。

算法框架：for (int i = 0; i ＜ n-1; i++) {//n-1趟

從a[i]檢查到a[n-1];

若最小的整數(shù)在a[k]， 交換a[i]與a[k];}

細(xì)化程序：void selectSort (int a[]， const int n) {

//對n個(gè)整數(shù)a[0]，a[1]，…，a[n-1]， 按非遞減順序排序

for (int i = 0; i ＜ n-1; i++) {

int k = i; //從a[i]檢查到a[n-1]， 找最小的整數(shù)， 在a[k]；

for (int j = i+1; j ＜ n; j++)

if ( a[j] ＜ a[k] ) k = j; //k指示當(dāng)前找到的最小整數(shù)

int temp = a[i]; a[i] = a[k]; a[k] = temp; //交換a[i]與a[k]

}}

算法求精，提高效率：void selectSort (int a[]， const int n) {

//對n個(gè)整數(shù)a[0]，a[1]，…，a[n-1]， 按非遞減順序排序

for (int i = 0; i ＜ n-1; i++) {

int k = i; //從a[i]檢查到a[n-1]， 找最小的整數(shù)， 在a[k]；

for (int j = i+1; j ＜ n; j++)

if (a[j] ＜ a[k]) k = j; //k指示當(dāng)前找到的最小整數(shù)

if(k＜＞i)

//找到的最小整數(shù)不是當(dāng)前序列中的第一個(gè)

{int temp = a[i]; a[i] = a[k]; a[k] = temp;}

//交換a[i]與a[k]}}

3 算法時(shí)間復(fù)雜度的大O表示法

對于有N個(gè)元素的數(shù)組，如果每一個(gè)元素搜索概率相等，那么搜索第1個(gè)元素要做1次比較，搜索第2個(gè)元素要做2次比較……，搜索第n個(gè)元素要做n次比較，從算法的整體看，搜索成功的平均比較次數(shù)為(n＋1)/2，因此找到一個(gè)函數(shù)f(n)=(n+1)/2，然后使用大O表示法T(n)=f(n)=O(n)來作為這個(gè)算法的時(shí)間復(fù)雜度的漸進(jìn)度量值。

要全面分析一個(gè)算法，要考慮算法在最壞情況下、最好情況下的時(shí)間代價(jià)和在平均情況下的時(shí)間代價(jià)。對于最壞情況用大O表示法來描述。算法的漸進(jìn)時(shí)間復(fù)雜度為T(n)=O(f(n))，算法的漸進(jìn)時(shí)間復(fù)雜度隨n變化。使用大O表示法要考慮關(guān)鍵操作的程序步數(shù)，找出其與n的函數(shù)關(guān)系g(n)，從而得到漸進(jìn)時(shí)間復(fù)雜度。

設(shè)g(n)＝2n3+2n2+2n+1，當(dāng)n充分大時(shí)，T(n)＝O(n3)，因?yàn)楫?dāng)n很大時(shí)2n2+2n+1可以忽略不計(jì)。因此，使用大O表示法時(shí)只保留最高次冪的項(xiàng)。

當(dāng)g(n)的數(shù)量級(jí)是對數(shù)級(jí)時(shí)，可能是log2n取下界或log2n取上界的線性關(guān)系，使用大O表示法，只要記為O(log2n)即可。數(shù)量級(jí)關(guān)系?。篶＜log2n＜n＜nlog2n＜n2＜n3＜2n＜3n＜n!；

大O表示法加法規(guī)則：針對并列程序段：T(n，m) = T1(n)+T2(m)=O(max(f(n)，g(m)))；

大O表示法乘法規(guī)則：針對嵌套程序段：T(n，m) = T1(n)*T2(m)=O(f(n)*g(m))；

算法時(shí)間復(fù)雜度的大O表示法分析實(shí)例1：

void example (float x[][]，int m，int n，int k) {

float sum [];

for (int i = 0; i ＜ m; i++) {//x[][]中各行

sum[i] = 0.0; //數(shù)據(jù)累加

for (int j=0; j＜n; j++) sum[i] += x[i][j];}

for (i = 0; i ＜ m; i++){ //打印各行數(shù)據(jù)和

cout ＜＜ \"Line\" ＜＜ i ＜＜

\": \" ＜＜sum [i] ＜＜ endl;}

兩個(gè)并列循環(huán)的漸進(jìn)時(shí)間復(fù)雜度為 O(max (m*n， m))；

算法時(shí)間復(fù)雜度的大O表示法分析實(shí)例2：

template ＜class Type＞ void dataList＜Type＞::bubbleSort() {//起泡排序的算法

//對表 Element[0] 到 Element[n-1]逐趟進(jìn)行比較， n是表當(dāng)前長度

int i = 1; int exchange = 1; //當(dāng)exchange為0則停止排序

while (i ＜ n exchange) {

BubbleExchange (i， exchange);

i++; } //一趟比較}

template ＜class Type＞void dataList＜Type＞::BubbleExchange(const int i， int exchange){

exchange = 0; //假定元素未交換

for (int j = ArraySize-1; j＞=i; j--)

if (Element[j-1] ＞ Element[j]) {

Swap (j-1，j); //發(fā)生逆序，交換Element[j-1]與Element[j]；

exchange = 1; //做“發(fā)生了交換”標(biāo)志

}}

漸進(jìn)時(shí)間復(fù)雜度為＜E:\\2008學(xué)術(shù)交流\\2008學(xué)術(shù)交流第二卷第五期(2008總第14期)\\第2次 28\\3軟件設(shè)計(jì)開發(fā)\\lj01.tif＞。

參考文獻(xiàn)：

[1] D E 克努特. 管紀(jì)文 譯. 計(jì)算機(jī)程序設(shè)計(jì)技巧3[M].北京:國防工業(yè)出版社，1999:185-190.

[2] 許卓群.數(shù)據(jù)結(jié)構(gòu)[M].北京:高等教育出版社，1993:103-108.

[3] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2004:207-215.