引言
Niklaus Wirth曾提出了一個程序公式：程序=數(shù)據(jù)結(jié)構(gòu)+算法芝雪。
算法是數(shù)據(jù)結(jié)構(gòu)的靈魂，這句話一點也不為過综苔。一個數(shù)據(jù)結(jié)構(gòu)設(shè)計的再好惩系，如果沒有算法，如同失去了靈魂的人如筛，它的存在就毫無意義堡牡。將算法和數(shù)據(jù)結(jié)構(gòu)結(jié)合起來，才能對數(shù)據(jù)結(jié)構(gòu)進行各種運算操作杨刨。
既然算法如此重要晤柄，我們接下來就學習一下什么是算法。
算法是什么
算法（algorithm）是解決特定問題的步驟描述妖胀，簡單的說芥颈，算法就是描述解決問題步驟的方法。
例如赚抡，新學期開學爬坑，學生從家到學校的交通方式這個問題就有很多種解決方案：
有的學生乘坐火車；
有的學生乘坐汽車涂臣；
有的學生乘坐飛機盾计；
距離學校很近的學生可能騎自行車或者做公共汽車；
有的學生可能步行就到學校了肉康。闯估。。
這些方案中的每一種就是一種算法吼和，這么多解決方法就是這么多種算法涨薪。
在計算機中，算法也是對某一個問題的求解方法炫乓，只是他的表現(xiàn)形式是計算機指令的有序序列刚夺，執(zhí)行這些指令就能夠解決特定的問題。
例如末捣，在高級程序設(shè)計語言中（C侠姑、C++、Java）箩做，常用的排序算法（冒泡排序莽红，選擇排序等）都是用計算機指令編寫算法，從而解決排序問題。
在程序設(shè)計中安吁，算法有3種較為常用的表示方法：
偽代碼法
N-S結(jié)構(gòu)化流程圖法
流程圖法
其中用的最多的是最后一種：流程圖法
流程圖法
流程圖是描述問題處理步驟的一種常用的圖形工具醉蚁，他由一些圖框和流程線組成。
使用流程圖描述處理問題的步驟鬼店，形象直觀网棍，便于閱讀。
畫流程圖時必須按照功能選用相應的流程圖符號妇智，常用的流程圖符號如下展示：
這里說明一下
* 起止框用于表示流程的開始或者結(jié)束滥玷，我們看到是一個圓邊矩形
* 輸入輸出框用平行四邊形表示，在平行四邊形內(nèi)可以寫明輸入或者輸出的內(nèi)容
* 判斷框用菱形來表示巍棱，它的作用是對條件進行判斷惑畴，根據(jù)條件的是否成立來決定如何執(zhí)行后續(xù)的操作
* 處理框用矩形表示，它代表程序中的處理功能航徙，如算術(shù)運算或者賦值等
* 流程線用單向箭頭或者直線表示桨菜，可以連接不同位置的圖框。流程線的標準流向是從左到右捉偏，從上到下，可以用直線表示泻红，非標準流向的流程線應使用箭頭指明方向夭禽。
* 連接點用圓形表示，用于流程圖的延續(xù)谊路。
ok,根據(jù)上邊的解釋讹躯，大家應該對流程圖有了一定的認識了吧，下方以一個選擇排序的算法流程圖為例缠劝，簡單學習一下流程圖的使用潮梯，如下圖：
解釋一下：
假設(shè)一個數(shù)組要從小到大排序，結(jié)合流程圖來分析選擇排序的過程：
第一步：在數(shù)組中選擇出最小的值惨恭，將它與角標0的元素進行交換秉馏，即放在開頭第一位
第二步：除角標為0的元素外，從剩下的待排序元素中選擇出最小的元素脱羡，將它與角標為1的元素進行互換萝究，即放在第二位
第三步：以此類推，直到完成最后兩個元素的排序交換锉罐，至此帆竹，完成了整個升序排列。
這樣脓规，根據(jù)流程圖來編寫算法的指令代碼栽连，就會變的很清晰。大家在以后設(shè)計算法時侨舆，可以先根據(jù)設(shè)計思路畫出算法的流程圖秒紧，其次分析其可行性绢陌，最后再完成代碼，這樣應該思路會更加清晰噩茄，代碼的bug也會少很多下面。
算法的特性
一個好的算法，尤其是一個成熟的算法绩聘，應該具備以下5個特性：
（1）確定性沥割。算法的每一步都有明確的含義，不會出現(xiàn)二義性凿菩。即在相同的條件下机杜，只有一條執(zhí)行路徑，相同的輸入只會產(chǎn)生相同的輸出結(jié)果衅谷。
（2）可行性椒拗。算法的每一步都是可執(zhí)行的，通過執(zhí)行有限次操作來完成其功能获黔。
（3）又窮性蚀苛。一個算法必須在執(zhí)行又窮步驟之后結(jié)束，且每一步都可以在又窮時間內(nèi)完成玷氏。這里的有窮概念不是數(shù)學意義上的堵未，而是指在實際應用中可以接受的，合理的時間和步驟盏触。
（4）輸入渗蟹。算法具有零個或多個輸入。有些輸入量需要在算法執(zhí)行過程中輸入赞辩；有的算法表面上沒有輸入雌芽，但實際上輸入量已經(jīng)被嵌入到了算法中了。
（5）輸出辨嗽。算法至少具有一個或多個輸出世落。“輸出”是一組與“輸入”具有對應關(guān)系的量值召庞，是算法進行信息加工后的到的結(jié)果岛心，而這種對應關(guān)系即算法的功能。
ok篮灼，一個好的算法需要具備這5個條件忘古。那么在設(shè)計算法時，怎樣才能設(shè)計出好的算法呢诅诱？這就需要在設(shè)計算法時有明確的目標髓堪。想要設(shè)計出一個好的算法，需要從以下4個方面來考慮：
（1）正確性。算法能夠正確的執(zhí)行干旁，實現(xiàn)預定的功能驶沼。這是算法最重要也是最基本的要求，它包含程序沒有語法錯誤争群；對于合法的輸入能夠產(chǎn)生滿足要求的輸出結(jié)果回怜；甚至對于非法的測試數(shù)據(jù)都能有滿足要求的輸出結(jié)果。一個好的算法必定經(jīng)得住千錘百煉的測試换薄。
（2）可讀性玉雾。算法應該易于理解，也就是可讀性好轻要，這就要求算法的邏輯必須是清晰复旬、簡單和結(jié)構(gòu)化的〕迥啵可讀性好有助于程序員理解算法驹碍，晦澀難懂的算法往往會隱藏錯誤且不易于被發(fā)現(xiàn)，難于測試和修改凡恍。
（3）健壯性志秃。要求算法具有高容錯性，即提供異常處理嚼酝，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行校驗檢查洽损，不經(jīng)常出異常中斷或者死機現(xiàn)象。
（4）高效率和低存儲革半。算法的效率通常指的是算法的執(zhí)行時間，對于同一個問題的多種算法流码，執(zhí)行時間段的其效率就高又官。存儲量指得是算法在執(zhí)行過程中所需的最大存儲空間，包括所用到的內(nèi)存和外存漫试。設(shè)計算法時應該考慮到執(zhí)行效率和存儲需求六敬，設(shè)計出一個“性價比”較高的算法。
ok,要設(shè)計出一個好的算法驾荣，就要綜合考慮其正確性外构、可讀性、健壯性播掷，還要考慮其執(zhí)行效率和存儲量需求审编。
算法的復雜度
分析一個算法主要看這個算法的執(zhí)行需要多少機器資源。在各種機器資源中歧匈，時間和控件是兩個主要的方面垒酬。因此，在進行算法分析時，人們最關(guān)心的就是運行算法所要花費的時間和算法匯總使用的各種數(shù)據(jù)所占用的空間資源勘究。
算法所花費的時間通常稱為時間復雜度矮湘，使用的空間資源稱為空間復雜度。
1口糕、時間復雜度
在進行算法分析時缅阳，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，然后分析T(n)隨n的變化景描。
T(n)=O(f(n))
這種用大寫的O來標記算法的時間復雜度十办，稱為大O（Order的縮寫）標記法。一般隨著n的增長伏伯，T(n)也會隨著增長橘洞，其中T(n)增長最慢者就是時間性能最優(yōu)的算法。
在計算時間復雜度的時候说搅，根據(jù)T(n)與n的最高階數(shù)關(guān)系炸枣，我們給這些算法的復雜進行了歸類，歸類情況如下表所示
除了上面的這幾種關(guān)系弄唧，當然還會有其他階數(shù)關(guān)系适肠，這里只是列出了幾個常見的關(guān)系。
算法的執(zhí)行次數(shù)可能會與規(guī)模n呈現(xiàn)出這些關(guān)系候引，那么這些關(guān)系又是如何推導出來的呢侯养？下面給出大O階的推導方法：
（1）用常數(shù)1取代運行中所有的加法常數(shù)
（2）在修改后的運行次數(shù)函數(shù)中，只保留最高階項
（3）如果最高階項存在澄干，且不是1逛揩，則除去其常系數(shù)，得到的結(jié)果就是大O階麸俘。
舉幾個例子
接下來通過分析幾段程序的執(zhí)行過程來推導出其時間復雜度
例1：
int a=100; //執(zhí)行一次
int b=200; //執(zhí)行一次
int sum=a+b; //執(zhí)行一次
printf(“%d\n”,sum); //執(zhí)行一次
上面程序段有4行代碼辩稽，每一行代碼執(zhí)行一次，加起來一共執(zhí)行了4次从媚，f(n)=4,即T(n)=O(4)逞泄。
根據(jù)推導方法中的第一條，將常數(shù)項用1代替拜效。在保留其最高階項時喷众，我們發(fā)現(xiàn)并沒有最高階項，因此該算法的時間復雜度是O(1),為常數(shù)階紧憾。
例2：
void function(){
int i,sum=0; //執(zhí)行1次
for(i=0;i<=100;i++){
sum+=i到千； //執(zhí)行n次
}
printf("%d\n",sum); //執(zhí)行1次
}
該程序段的執(zhí)行次數(shù)為1+n+1，即f(n)=n+2赴穗。然后根據(jù)規(guī)則父阻，我們把數(shù)項用1代替愈涩，且只保留到最高階，則得出T(n)=O(n),因此這個算法的時間復雜度為O(n)加矛，為線性階履婉。
例3：
void func(){
int i=1;
do
{
i*=2;
}
while(i<n);
}
在這個程序段中，當i<n時斟览，程序循環(huán)結(jié)束毁腿。如果循環(huán)了f(n)次，則就有這樣的情況
2f(n)=n
那么我們計算一下f(n)為多少
f(n)=log2n
即我們得知這個算法的時間負責度為
T(n)=O(log2n)苛茂。
我們根據(jù)規(guī)則已烤，將常系數(shù)消除，爆了最高階妓羊，最后得出
T(n)=O(logn)胯究，為對數(shù)階。
用大O階來推導算法的復雜度并不難躁绸，我們在以后學習中設(shè)計算法裕循，多數(shù)就可以用這種方法來估測算法的優(yōu)劣。當然我們以后談算法的復雜度時净刮，也是以大O階來判定的剥哑。
2、空間復雜度
空間復雜度是對一個算法在運行過程中所占用的存儲空間的大小的度量淹父，一般也作為問題規(guī)模n的函數(shù)株婴，以數(shù)量級形式給出，格式如下：
S(n)=O(f(n))
一個算法的存儲量包括輸入數(shù)據(jù)所占空間暑认、程序本身所占空間和輔助變量所占空間困介。在對算法進行分析時，只考慮輔助變量所占空間蘸际。
若所需輔助空間相對于輸入數(shù)據(jù)量來說是常數(shù)逻翁，則稱此算法為原地工作。
若所用空間量依賴于特定的輸入捡鱼，則除了有特殊說明之外，均按最壞情況考慮酷愧。
有時候驾诈，在寫代碼時可以
用空間來換取時間
例如：
寫一個算法來判斷某年是否是閏年，這樣每輸入一個年份都要去調(diào)用算法判斷一下溶浴，在時間上就有點復雜了乍迄。為了提高效率，可以用空間來換取時間士败，即建立一個大小合適的數(shù)據(jù)闯两，編號從0到n褥伴，如果是閏年，則存入數(shù)據(jù)1漾狼，否則存入數(shù)據(jù)0重慢。這樣只要通過判斷年份編號上存儲的是0還是1就知道該年份是否是閏年了。
用空間換取時間可以將運算最小化逊躁，但是到底需不需要這樣做似踱，還得結(jié)合實際情況來定。
一般情況下稽煤，都是用時間復雜度來度量算法核芽，當不加限定地使用“復雜度”這一術(shù)語時，都是指時間復雜度酵熙。
總結(jié)
計算機軟件的最終成果都是以程序的形式體現(xiàn)的轧简，一個程序應該包含以下兩方面的內(nèi)容：
（1）對數(shù)據(jù)的描述。在程序中指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式匾二，也就是數(shù)據(jù)結(jié)構(gòu)哮独。
（2）對數(shù)據(jù)操作的描述。即操作步驟假勿，也就是算法借嗽。
數(shù)據(jù)結(jié)構(gòu)算法的基礎(chǔ)，算法是數(shù)據(jù)結(jié)構(gòu)的靈魂转培。數(shù)據(jù)結(jié)構(gòu)設(shè)計和算法分析的目的是設(shè)計更好的程序恶导。
程序的本質(zhì)是為要處理的問題選擇好的數(shù)據(jù)結(jié)構(gòu)，同時在此結(jié)構(gòu)上施加一種好的算法浸须。
數(shù)據(jù)存儲結(jié)構(gòu)會影響算法的好壞惨寿，因此在選擇存儲結(jié)構(gòu)時，也要考慮其對算法的影響删窒。例如裂垦，如果存儲結(jié)構(gòu)的存儲能力較強，則可以存儲較多的信息肌索，算法將會好設(shè)計一些蕉拢。反之，對于過于簡單的數(shù)據(jù)結(jié)構(gòu)诚亚，基于該結(jié)構(gòu)的算法設(shè)計可能會比較復雜一些晕换。
總之一句話：
選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法，會讓我們事半功倍~
