摘要：隨著計算機的發(fā)展，算法在計算機方面已有廣泛的發(fā)展及應(yīng)用。算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量。通過計算機語言進(jìn)行編程，善于運用算法，可以減少代碼，提高效率，達(dá)到事倍功半的效果本文以C語言編程語言為編程工具，對于數(shù)組中求最大子數(shù)組的題目，通過窮舉法（暴力法）、分治法、分析法以及動態(tài)規(guī)劃法等算法進(jìn)行了對比說明。

關(guān)鍵詞：算法? 最大子數(shù)組 暴力法 分治法 分析法? 動態(tài)規(guī)劃法

中圖分類號：? TP301.6? ? ? ? 文獻(xiàn)標(biāo)志碼：A

1 C語言簡介

C語言（The C Programming Language）是一門面向過程、抽象化的通用程序設(shè)計語言，廣泛應(yīng)用于底層開發(fā)。C語言僅僅產(chǎn)生少量的機器語言，而且不需要任何運行環(huán)境支持，就能夠運行的高效率程序設(shè)計語言。C語言具有跨平臺的特性，以一個標(biāo)準(zhǔn)規(guī)格寫出的C語言程序可在包括一些類似嵌入式處理器以及超級計算機等作業(yè)平臺的許多計算機平臺上進(jìn)行編譯。

1972年，美國貝爾實驗室的 丹尼斯·里奇（D.M.Ritchie 設(shè)計出了C語言。美國電話電報公司（AT&T）貝爾實驗室于1978年正式發(fā)表了C語言。布萊恩·柯林漢（Brian Kernighan） 和 丹尼斯·里奇（Dennis Ritchie）出版了《The C Programming Language》一書。C語言編譯器普遍存在于各種不同的操作系統(tǒng)中，例如Microsoft Windows， Mac OS X， Linux， Unix等。C++、Objective-C、Java、C#等編程語言都深受C語言的設(shè)計影響。經(jīng)過多年的改進(jìn)和完善，C語言的標(biāo)準(zhǔn)先后有ANSI X3.159-1989 "Programming Language C（C89標(biāo)準(zhǔn)（ANSI C））、ISO/IEC 9899：1990 - Programming languages – C（C90標(biāo)準(zhǔn)）、ISO/IEC 9899：1990/Cor 1：1994（C94）標(biāo)準(zhǔn)、ISO/IEC 9899：1990/Amd 1：1995 - C Integrity（C95標(biāo)準(zhǔn)）、ISO/IEC 9899：1999 - Programming languages -- C （C99標(biāo)準(zhǔn)），目前最高標(biāo)準(zhǔn)為ISO/IEC 9899：2011 - Information technology -- Programming languages -- C ， （C11標(biāo)準(zhǔn)））。目前，長期占據(jù)著程序使用榜的前三名為C，C++，java同一系的語言。

1.1 C語言的優(yōu)點

C語言自發(fā)布以來，深受廣大程序員的青睞，而經(jīng)久不衰，是與其許多優(yōu)點有關(guān)。C語言具有以下優(yōu)點：語言簡潔緊湊、靈活方便;運算符以及數(shù)據(jù)類型豐富;編程表達(dá)方式靈活實用;可以允許直接訪問物理地址，能夠?qū)τ布M(jìn)行操作;不僅生成目標(biāo)代碼質(zhì)量高，程序執(zhí)行效率高，而且可移植性好、表達(dá)力強等優(yōu)點。

1.2 C語言的缺點

正如人無完人，金無赤金一樣，在長期的應(yīng)用實踐中，大家也發(fā)現(xiàn)C語言也有一些缺點和不足。C語言在數(shù)據(jù)的安全性上有很大缺陷，主要表現(xiàn)在數(shù)據(jù)的封裝性上。此外C語言對變量的類型約束和語法限制不嚴(yán)格，對數(shù)組下標(biāo)越界不作檢查等，影響了程序的安全性。從應(yīng)用的角度，C語言比其他高級語言較難掌握。

2 算法簡述

2.1 算法的基本概念

算法（Algorithm）與程序設(shè)計以及數(shù)據(jù)結(jié)構(gòu)（Data Structures）緊密相關(guān)，是解決一個問題的完整的步驟描敘，是解決問題的策略，規(guī)則，方法，算法的描敘形式多種多樣，常用的有自然語言、結(jié)構(gòu)化流程圖、偽代碼和PAD圖等，其中最普遍的是流程圖。

瑞士計算機科學(xué)家Pascal之父Nicklaus Wirth（沃斯）提出的著名公式：“算法+數(shù)據(jù)結(jié)構(gòu)=程序”（Algorithm+Data Structures=Programs）。數(shù)據(jù)結(jié)構(gòu)值得是數(shù)據(jù)與數(shù)據(jù)之間的邏輯關(guān)系，算法則指的是解決特定問題的步驟和方法。算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機化算法、并行算法，厄米變形模型，隨機森林算法。

2.2 算法的特征

一個算法應(yīng)該具有以下五個重要的特征：算法的基本特征歸納如下：

2.2.1 有窮性（Finiteness）是指算法必須能在執(zhí)行有限個步驟之后終止;

2.2.2 確切性（Definiteness） 即算法的每一步驟必須有確切的定義;

2.2.3 輸入項（Input） 一個算法有0個或多個輸入，以描述運算對象的初始情況，所謂0個輸入是指算法本身給定出了初始條件;

2.2.4 輸出項（Output） 相對于輸入項，一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。值得一提的是，沒有輸出的算法是毫無意義的;

2.2.5可行性（Effectiveness） 算法中執(zhí)行的任何步驟都是可以被分解為基本的可執(zhí)行的操作步驟，也就是說每個計算步驟都可以在有限時間內(nèi)完成，因此同樣稱之為有效性。

3 求最大子數(shù)組的四種算法示例

數(shù)組是定義用來存儲個組同一種數(shù)據(jù)的構(gòu)造，特定是只能存放一種類型的數(shù)據(jù)，數(shù)組里的數(shù)據(jù)稱為元素。數(shù)組可以是一維數(shù)組、二維數(shù)組以及多維數(shù)組。

最大連續(xù)子數(shù)組：假設(shè)給定一個數(shù)組Array[0，...，n-1]，該數(shù)組有n個元素，求Array的連續(xù)子數(shù)組，使得該子數(shù)組的和最大。

下面給出運用四種不同算法求最大連續(xù)子數(shù)組的解法。

3.1 窮舉法（暴力法）

或稱為暴力破解法，其基本思路是：對于要解決的問題，列舉出它的所有可能的情況，逐個判斷有哪些是符合問題所要求的條件，從而得到問題的解。

算法分析：直接求解Array[i，...j]的值;其中0<=i<n;i<=j<n，i，i+1，...，j-1，j的最大長度為n;即對數(shù)組內(nèi)每一個數(shù)A[i]進(jìn)行遍歷，然后遍歷以它們?yōu)槠瘘c的子數(shù)組，比較各個子數(shù)組的大小，找到最大連續(xù)子數(shù)組。代碼如下：

#include "stdafx.h"

//暴力法求最大子數(shù)組和問題

int _tmain（int argc， _TCHAR* argv[]）

{

int A[8] = { -6， 10， -5， -3， -7， -1， -1 };

int array_length = sizeof（A） / sizeof（A[0]）;//數(shù)組大小

int sum = 0;//記錄子數(shù)組的和

int low;//記錄子數(shù)組的底

int height;//記錄子數(shù)組的高

for （int i = 0; i < array_length; i++）

{

for （int j = i ; j < array_length; j++）

{

int subarraysum=0;//所遍歷出來的子數(shù)組的和

//計算遍歷的子數(shù)組之和

for （int k = i; k <= j; k++）

{

subarraysum += A[k];

}

//找出最大的子數(shù)組

if （subarraysum>sum）

{

sum = subarraysum;

low = i;

height = j;

}

}

}

printf（"%d? %d? %d"， low， height，sum）;//將結(jié)果打印出來

getchar（）;

return 0;

}

可以看到這段程序里面一共嵌套著三層循環(huán)，除了最外面的循環(huán)會循環(huán)n次外，內(nèi)部的循環(huán)都比n次小，此程序的時間復(fù)雜度為O（n3）

3.2 分治法

分治法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

算法分析：將數(shù)組從中間分開，這樣最大子數(shù)組要么完全在左半邊數(shù)組，要么完全在右半邊數(shù)組，要么跨立在分界點上。如果完全在左半邊數(shù)組或者右半邊數(shù)組的話，可以采用遞歸解決。如果跨立在分界點上，實際上是左半邊數(shù)組的最大后綴和右半邊數(shù)組的和。因此，從分界點向前掃，向后掃就可以了。代碼如下：

double? MaxaddSub（double *a， int from， int to）

{

if（to == from）

return a[from];

int middle = （from + to）/2;

double m1 = MaxaddSub（a，from，middle）;

double m2 = MaxaddSub（a，middle+1，to）;

int i， left = a[middle]， now=a[middle];

for（i = middle-1; i>=from; --i）

{

now += a[i];

left = max（now，left）;

}

int right = a[middle_1];

now = a[middle+1];

for（i = middle+2;i<= to; +=i）

{

now ==a[i];

right = max（now， right）;

}

double m3 = left + right;

return max（m1，m2，m3）;

}

分治法算法復(fù)雜度分析：首先已經(jīng)知道算法的遞歸關(guān)系為：T（n）=2*T（n/2）+cn，c為常數(shù)。若n=2k，則有：

T（n）=2*T（n/2）+cn

=2*（2*T（n/4）+c*（n/2））+c*n=4*T（n/4）+2c*n

=4*（2*T（n/8）+c*（n/4））+2c*n）=8*T（n/8）+3c*n

=8*（2*T（n/16）+c*（n/8））+3c*n）=16*T（n/16）+4c*n

=……

=2k T（1）+kc*n

=cn+cnlog_2?n

若2k<n<2k+1，則T（2k）<T（n）<T（2k+1），所以可以得出算法的時間復(fù)雜度T（n）=O（nlogn）。由于本程序是在數(shù)組的原地址上面進(jìn)行的，所以總體的控件復(fù)雜度為遞歸的時間復(fù)雜度+數(shù)組所占的空間為S（n）+S（logn）=S（n）。

3.3 分析法（邏輯推理的算法應(yīng)用）

算法分析：定義數(shù)組A的前綴和p[i] = a[0] + a[1]+...+a[i]， 從i到j(luò)的子數(shù)組和s[i，j] = p[j]-p[i-1]（這里定義p[-1]=0）。算法過程如下：首先求一個數(shù)組A的i前綴的和p[i]，遍歷i，這里0<=i<=n-1，那么p[i]=p[i-1]+A[i]然后計算p[i]-p[j]，遍歷i，同樣0<=i<=n-1，求一個最小值m，m的含義到當(dāng)前i為止，從0到i-1這段最小的值，值的初始值設(shè)定為0（p[-1]=0），然后遍歷p[0，...，i-1]，更新m。則p[i]-m即為以a[i]結(jié)尾的數(shù)組中最大的子數(shù)組。關(guān)鍵代碼如下：

int m=0;

for（int i=0;i<n;==i）

{

if（a[i] - m > MaxV）

MaxV = a[i] - m;

if（m < a[i]）

m = a[i];

}

由于以上兩步都是線性的，因此，時間復(fù)雜度為O（n）。

3.4 動態(tài)規(guī)劃法

動態(tài)規(guī)劃是一種在數(shù)學(xué)和計算機科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計算機科學(xué)和工程領(lǐng)域。

算法分析：假定S[i]為以A[i]結(jié)尾的數(shù)組中和最大的子數(shù)組，那么，S[i+1]=max（S[i]+A[i+1]，A[i+1]）），S[0]=A[0]，i（0<=i<n-1）。代碼如下：

#include <stdlib.h>

#include? <stdio.h>

int main（）

{

int count;

int a[100];

int b[100];

int i;

int max;

scanf（"%d"，&count）;

for（i=0; i<count; i++）

{

scanf（"%d"，&a[i]）;

}

b[0]=a[0];

max=b[0];

for（i=1; i<count; i++）

{

if（b[i-1]>0）

b[i]=b[i-1]+a[i];

else

b[i]=a[i];

if（b[i]>max）

max=b[i];

}

printf（"%d＼n"，max）;

return 0;}

該算法的時間復(fù)雜度O（n）。

4 結(jié)束語

算法可以說包羅萬象，諸如推理、邏輯、演繹、歸納、類別等方法。常用的算法有遞推法、遞歸法、窮舉法、貪心算法、分治法、動態(tài)規(guī)劃法、迭代法、分支界限法、回溯法等諸多方法。一個算法的好壞直接決定了這個程序的好壞，合理地運用算法，能夠獲得更高的效率。掌握和熟悉這些算法技巧，對于計算機編程設(shè)計是大有裨益的。

參考文獻(xiàn)：

[1] 譚浩強.C程序設(shè)計：第4版[M].北京：清華大學(xué)出版社，2010.

[2] 蘇小紅，孫志崗，陳惠鵬.C語言大學(xué)實用教程[M].北京：電子工業(yè)出版社，2012.

[3] 毛廣敏.常用C語言排序算法解析[J].軟件導(dǎo)刊，2012 ， 11（11）：51-54.

[4] Michael Wong，IBM XL 編譯器中國開發(fā)團(tuán)隊.深入理解C++11： C++11新特性解析與應(yīng)用[M].北京：機械工業(yè)出版社，2013.

[5] 徐鳳生，黃超，謝玉華.C語言程序設(shè)計[M].北京：中國鐵道出版社，2015.

[6] Wirth Niklaus.算法+數(shù)據(jù)結(jié)構(gòu)=程序[M].曹德和，劉椿年，譯.北京：科學(xué)出版社，1984.

[7] Cormen Thomas H. ，Leiserson Charles E. ，Rivest Ronald L. ，et al.算法導(dǎo)論：第3版[M].殷建平，徐云，王剛，譯 .北京：機械工業(yè)出版社，2015.

[8] 鐘志水，姚珺.大學(xué)計算機應(yīng)用基礎(chǔ)[M].重慶：重慶大學(xué)出版社，2012：213-214.

劉柱（1971—），男，漢族，甘肅蘭州人，大學(xué)本科，工程師，主要從事網(wǎng)絡(luò)工程軟件開發(fā)工作。