從零開始_學_資料結構（一）——算法的基本概念

從零開始_學_資料結構（一）——算法

算法的定義：

解決問題的方法。

對于同一個問題，一個好的算法比一個差的算法，效率更高，更節約資源。

for computer：算法是解決特定問題的求解步驟的描述，在計算機中，表示指令的有限序列，每條指令表示一個或者多個操作。

簡單來說，算法就是輸入代碼，告訴計算機，你應該怎麼解決這個問題。

算法的特性：

（1）輸入和輸出。

       光算出結果但不輸出結果，跟沒算沒差別；要計算，總得有資料，不然沒法計算。

（2）有窮性：

       能出結果，并且在接受時間之内出結果。如果時間太長，這個算法往往就沒什麼意義了。

（3）确定性：

       同樣的資料，同一個算法，出同樣的結果。

（4）可行性；

       如果一個算法太複雜，都沒辦法變成代碼給計算機，那肯定不行。

一個好的算法的要求：

（1）正确。

對于計算的資料，能得到預期的結果。

①首先得做到程式沒問題，能運作；

②其次得對于計算的資料，能得到符合要求的結果；

③更好的算法，對于非法資料，能得出滿足要求的結果（比如說提示有問題）；

④對于專門用于為難人的資料，也能有滿足要求的輸出結果；

至少要做到第②步

（2）可讀性

代碼和算法，起碼讓人能讀懂，不然寫代碼的人都不明白自己寫的代碼，如果代碼出問題，那麼也沒辦法鑒别出來。

（3）健壯性

面對不符合要求（非法）的資料，能夠适當的處理。

例如，我們正常處理的一組資料裡，隻有正數，比如說我們使用unsigned int類型。那麼假如有負數輸入，如果沒有代碼去鑒别這些，那麼就容易出現出乎意料的結果。

（4）速度快，用記憶體小

假如計算一組1gb大小的資料，同樣的處理器

①假如一個算法用1分鐘，另一個算法用1小時，顯然前者更好；

②假如一個算法用10mb記憶體，另一個算法用1gb記憶體，顯然前者更好。

在實際中，有時候會出現對于較少的資料來說，某一種算法更好，對于較多的資料來說，另一種算法更好。是以，選擇哪種算法，要根據實際情況而決定。

算法效率的度量方法：

（1）事後統計：

簡單直接，運作一遍就知道。

他到底用1秒還是100秒，用10mb記憶體還是500mb記憶體，一目了然。

缺點：假如需要1天甚至10天難道也要這麼做？肯定是不靠譜的。是以，一般是不會使用這種方法的。

（2）事前分析估算方法：

這個方法，簡單來說，就是：

①預估資料量（比如100萬個資料）

＋

②根據算法計算其運作次數（比如說３行代碼，一般是運算３次的。但若涉及到循環，那麼就是循環代碼的行數＊循環次數）

③機器執行代碼的速度（計算求和與在一串字元串中插入一個字元，其執行速度自然是有差別的。而且，機器配置不同，運作同樣指令其時間也是有差別的）

由于③是不可控的，是以一般不考慮。

而①是我們要為之服務的對象，是以是需要考慮，但無法選擇的；

隻有②，是我們最需要關心的内容。

以循環為例：

int total;

for(int i=0; i < n; i ++)

{

       cin>>data[i];

       data[i]*=2;

       data[i]+=5;

       total += data[i];

}

       cout<< total;

//假如cin是讀取某個檔案的int類型的資料（實際上不能這麼寫）

首先，循環範圍内有4條指令。是以，當data數組裡有n個元素時，這個代碼将執行4*n + 2次，4*n是循環，1是int total，另一個1是cout<<total。

如果我們使用另外一個方法：

for(int i=0; i<n; i++)

       total+=data[i];

total=total*2+5*n;

cout<<total;

//注意，這裡的cin隻是用來意會，實際應用ifstream類變量來讀取檔案

與上面相比，這個算法需要執行的次數是：2*n+3次。

假如n=100萬時，第一個算法需要執行的次數是400萬+2次，第二個算法執行的次數是200萬+3次，節約了幾乎50%的時間。

這樣的話，哪個算法好，通過簡單的預估執行代碼的次數，一目了然。

當然了，實際中，會因為代碼不同，不同的代碼的效率略有差異，但是顯然執行次數更少的代碼，更剩時間，效率也更高。

除了以上兩種以外，還有雙重for循環（即外層是一個for循環，執行n次；然後在外層的for循環内部還有一個for循環，執行m次，如代碼）；

for (int i=0; i < n ; i++)

       for(int j=0; j<m; j++)

              total=total+m+n;

這樣一段代碼，其執行次數将為m*n次（假如m=n的話，可以認為其運作次數為n的乘方）。

總結一下：

不同的算法（假設代碼行數為m），針對不同的資料量（n），将執行不同的次數：

有的次數為n，有的次數為m，有的為m*n，有的為n*n，也有其他的。

一般來說，需要特别設計算法的，資料量都比較大（比如說幾萬甚至更多），代碼行數相對就偏少（也許隻有幾行或者幾十行）。

是以，m次最好，n次其次，m*n次再次，n*n次最次。

四個字：避免乘方

如下表：

資料量n

算法a執行代碼（n2）次

記作f(a)=

算法b執行代碼（3n）次

f(b)=

1

3

2

4

6

9

10

100

30

一萬

三百

10000

一億

三萬

假如需要特别的算法，一般來說，原因是資料量都很大（幾百mb，幾gb，幾十幾百gb，甚至tb級别），隻有一個好的算法，才能做到高效率的完成任務。

是以，需要盡量避免那種執行的代碼次數，為資料量的乘方甚至n次方這樣的情況。

以下概念有印象就行，反正知道怎麼用最重要，單純背概念毫無意義。

概念：函數的漸進增長

如上表，當n<3時，f(a)>f(b)；

當n=3時，f(a)=f(b)；

當n>3時，f(a)>f(b)；

假如對于給定的函數，存在一個整數n，使得對于所有n>n的情況，f(a)總是大于f(b)，那麼我們就說，f(a)的漸進增長快于f(b)

假如兩個函數，都存在幂的情況（比如說n的2次方或者3次方）。

那麼主要關心其最高階的部分（因為假如n=10，其2次方的值，僅僅隻有3次方的十分之一，n越大，差距越大。即使一個是n的平方+一萬，另一個是n的3次方，隻需要n=100時，前者的效率便能輕松高于後者）。

是以：避免使用需要執行n的m次方次代碼的算法。

除此之外，一個算法的需要執行代碼的次數還有對數的情況、或者是指數的情況。

個人意見是，這裡有個概念就可以，暫時不需要深究，畢竟這裡學的是資料結構。

算法需要考慮最壞的情況：

例如我們設計一個算法，然後通過這個算法去試圖去尋找一個檔案裡的資料。

那麼①這個資料可能存在于檔案的開始，也可能存在于資料的結尾；

②如果這個算法是逐個位元組尋找，那麼假如在開始，就會立刻找到，但若假如在結尾，那麼可能需要找很久很久。而這個

最壞的情況（需要很多時間），是需要我們考慮的。

③特别是當這個檔案很大很大時（周遊整個檔案需要很多時間），那麼考慮如何解決這個問題，是很重要的（是以可能需要優化算法）。比如說，假如這個資料存在的開始位址，是0xxxxx0這樣，我們就可以考慮一次讀取十六個位元組，然後先對比第一個，符合後在繼續對比，這樣的話，就相對節約了很多時間。

④除了優化算法外，我們還應該考慮平均時間。例如，當算法無法優化時，那麼最好的情況下，這個算法需要多久，最差的情況下，這個算法需要多久，二者平均起來，往往就是普通的情況下，需要的時間。

而這個 平均時間，是這個算法的期望運作時間，是需要我們關注的。

算法的存儲空間：

當使用算法時，除了需要花時間外，可能還需要使用一定的存儲空間。

例如：

①使用一個10個元素的int數組來存儲計算的内容，由于一個int是4位元組，是以需要使用40位元組來存儲這些内容；

②可能還要建立一個臨時的變量（堆或者棧）用于存儲算法中建立的臨時對象，而在提高效率方面，建立的臨時對象是有一定意義的；

③有時候，對于算法，要求其最多隻能使用多少空間，算法在運作過程中，不能超出這個界限。

是以，對于存儲空間的使用，也是有必要考慮的。

 第二章：樹

http://blog.csdn.net/qq20004604/article/details/50869632