淺析算法設計與算法時間復雜度

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

關鍵詞：算法；算法設計；時間復雜度

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)14-20878-03

1 算法的定義與特性

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

2 算法的描述

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

算法的描述原則：自頂向下、逐步求精的結構化程序設計方法。

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

選擇排序的基本思想是：每一趟（例如第i趟，i = 0，1，…，n-2）在后面n-i個待排序對象中選出關鍵碼最小的對象， 作為有序對象序列的第i個對象。待到第n-2趟作完，待排序對象只剩下1個，就不用再選了。

基本步驟是：

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

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

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

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

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

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

//對n個整數(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指示當前找到的最小整數(shù)

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

}}

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

//對n個整數(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指示當前找到的最小整數(shù)

if(k＜＞i)

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

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

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

3 算法時間復雜度的大O表示法

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

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

設g(n)＝2n3+2n2+2n+1，當n充分大時，T(n)＝O(n3)，因為當n很大時2n2+2n+1可以忽略不計。因此，使用大O表示法時只保留最高次冪的項。

當g(n)的數(shù)量級是對數(shù)級時，可能是log2n取下界或log2n取上界的線性關系，使用大O表示法，只要記為O(log2n)即可。數(shù)量級關系取：c＜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))；

算法時間復雜度的大O表示法分析實例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;}

兩個并列循環(huán)的漸進時間復雜度為 O(max (m*n， m))；

算法時間復雜度的大O表示法分析實例2：

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

//對表 Element[0] 到 Element[n-1]逐趟進行比較， n是表當前長度

int i = 1; int exchange = 1; //當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ā)生了交換”標志

}}

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

參考文獻：

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

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

[3] 嚴蔚敏.數(shù)據(jù)結構[M].北京:清華大學出版社，2004:207-215.