文章目錄
轉眼大學畢業已經一年多，計算機專業四大基礎課——《資料結構》、《計算機網絡》、《計算機組成原理》、《作業系統》，當時學的實在馬虎，到現在已經快要還完了。“基礎不牢，地動山搖”，曾經偷過的懶，現在都得給它補回去。
圖一：資料結構概覽
1968 年， 美國的高德納（ Donald E.Knuth) 教授在其所寫的《計算機程式設計藝術》 第一卷《 基本算法》 中， 較系統地闡述了資料的邏輯結構和存儲結構及其操作，開創了資料結構的課程體系。
70 年代初， 出現了大型程式， 軟體也開始相對獨立， 結構程式設計成為程式設計方法學的主要内容， 人們越來越重視 “資料結構” ， 認為程式設計的實質是對确定的問題選擇一種好的結構， 加上設計一種好的算法。
程式設計 = 資料結構 + 算 法
- 資料：是描述客觀事物的符号， 是計算機中可以操作的對象， 是能被計算機識别， 并輸入給計算機處理的符号集合。
- 資料元素： 是組成資料的、 有一定意義的基本機關， 在計算機中通常作為整體處理。 也被稱為記錄。
- 資料項： 一個資料元素可以由若幹個資料項組成。
- 資料對象： 是性質相同的資料元素的集合， 是資料的子集
來重點看看什麼是資料結構：
結構， 簡單的了解就是關系， 比如分子結構， 就是說組成分子的原子之間的排列方式。 嚴格點說， 結構是指各個組成部分互相搭配和排列的方式。 在現實世界中， 不同資料元素之間不是獨立的， 而是存在特定的關系， 我們将這些關系稱為結構。
那資料結構是什麼？
資料結構： 是互相之間存在一種或多種特定關系的資料元素的集合。
在計算機中， 資料元素并不是孤立、 雜亂無序的， 而是具有内在聯系的資料集合。 資料元素之間存在的一種或多種特定關系， 也就是資料的組織形式。
資料元素之間存在一種或多種特定關系，接下來就看看這個關系指的是什麼關系。
按照視點的不同， 我們把資料結構分為邏輯結構和實體結構。
邏輯結構展現的是資料元素之間的邏輯關系， 換句話說就是從操作對象中抽象出來的數學模型， 是以又稱為抽象結構， 通常我們習慣說的資料結構一般就是指的邏輯結構。
下面是幾種邏輯結構：
圖二：集合結構
圖三：線性結構
圖四：樹形結構
圖五：圖形結構
實體結構結構是資料在計算機内的存儲形式， 又稱存儲結構。 它包括資料元素的表示和關系的表示。
資料元素的存儲結構形式有兩種： 順序存儲和鍊式存儲。
- 順序存儲
順序存儲結構是把資料元素存放在位址連續的存儲單元裡， 其資料間的邏輯關
系和實體關系是一緻的。
圖六：順序存儲
- 鍊式存儲
鍊式存儲結構是把資料元素存放在任意的存儲單元裡， 這組存儲單元可以是連續的， 也可以是不連續的。 資料元素的存儲關系并不能反映其邏輯關系。
圖七：鍊式存儲
先來看看算法的定義：
算法是解決特定問題求解步驟的描述， 在計算機中表現為指令的有限序列， 并且每條指令表示一個或多個操作。
通俗來說，算法是指解決問題的一種方法或者一個過程。 一個問題可以用多種算法來解決， 一個給定的算法解決一個特定的問題。
那麼資料結構和算法有什麼關系呢？算法和資料結構是焦不離孟的關系。
不了解施加于資料上的算法需求就無法決定資料結構； 反之算法的結構設計和選擇又依賴于作為其基礎的資料結構。
即資料結構為算法提供了工具。 算法利用這些工具來實施解決問題的最優方案。
在計算機領域内， 一個算法實質上是根據處理問題的需要， 在資料的邏輯結構和存儲結構的基礎上施加的一種運算。
因為資料的邏輯結構和存儲結構不是惟一的， 是以算法的描述可能不惟一。 即使邏輯結構和存儲結構相同， 算法可能也不惟一。 通過學習資料結構，可以使得程式設計者選擇一種比較好的算法。
算法具有五個基本特性： 輸入、 輸出、 有窮性、 确定性和可行性。
- 輸入/輸出
輸入和輸出特性比較容易了解， 算法具有零個或多個輸入。 盡管對于絕大多數算法來說， 輸入參數都是必要的， 但對于個别情況， 如列印 “hello world!”這樣的代碼， 不需要任何輸入參數， 是以算法的輸入可以是零個。 算法至少有一個或多個輸出， 算法是一定需要輸出的， 不需要輸出， 那這個算法就沒有意義了。
-
有窮性
算法在執行有限的步驟之後， 自動結束而不會出現無限循環， 并且每一個步驟在可接受的時間内完成。 現實中經常會寫出死循環的代碼， 這就是不滿足有窮性。
- 确定性
算法的每一步驟都具有确定的含義， 不會出現二義性。 算法在一定條件
下， 隻有一條執行路徑， 相同的輸入隻能有唯一的輸出結果。 算法的每個步驟被精确
定義而無歧義。
- 可行性
算法的每一步都必須是可行的， 也就是說， 每一步都能夠通過執行有限次數完成。 可行性意味着算法可以轉換為程式上機運作， 并得到正确的結果。
設計一個好的算法通常應考慮達到以下目标：正确性、可讀性、健壯性、效率與低存儲量需求。
算法是解決計算問題的工具。 算法的好與壞直接影響解決問題的效率， 為提高解決問題的效率， 針對一個具體問題的解決方法， 除了需要考慮對算法的具體描述外， 還應具有衡量該算法好壞的方法。
算法的分析主要是指判斷算法的優劣， 判斷一個算法的好壞一般從兩個方面考慮， 即從時間角度和從空間角度上衡量算法。 一般算法分析從時間角度考慮的比較多。 當然判斷一個算法的好與壞， 也不能隻以時間或空間衡量簡單化， 而應該根據實際情況綜合考慮。
算法度量主要有這兩個方法：
- 事後統計方法
這種方法的缺點是， 必須先運作依據算法編制的程式； 所花時間的統計量依賴于計算機的軟體、 硬體等環境因素， 容易掩蓋算法本身的優劣。 是以人們常用第 2 種方法。
- 事前分析估算方法
一個用進階語言編寫的程式在計算機上運作時所消耗的時間取決于下列因素：
• 算法選用何種政策
• 問題規模
• 書寫程式的語言
• 編譯産生的機器代碼品質
• 機器執行指令的速度
當然，抛開硬體方向來講，算法效率依賴于問題的規模， 或者說， 它是問題規模的函數。
但在實踐中， 我們可以把兩種方法結合起來使用。一般地， 我們将算法的求解問題的輸入稱為問題的規模， 并用一個整數 n 表示。 例如， 矩陣乘積問題的規模是矩陣的階數， 而一個圖論問題的規模則是圖中的頂點個數或
邊的條數。
在算法的每個步驟中， 可能有若幹條語句， 而頻度就是指每條語句的執行次數。 一個算法的時間複雜度是指算法的時間耗費。
簡單地說， 就是以一條基本語句的執行時間為基本機關， 該算法所有語句中總的基本語句的執行次數就是該算法的時間耗費， 它是該算法所求解的問題規模n的函數。 當問題的規模n趨向無窮大時， 我們把時間複雜度的數量階稱為算法的漸進時間複雜度。
算法時間複雜度定義：
在進行算法分析時， 語句總的執行次數 T ( n ) 是關于問題規模 n 的 函 數 。 進 而 分 析 T ( n ) 随 n 的變化情況并确定 T ( n ) 的 數 量級。 算法的時間複雜度，也就是算法的時間量度， 記作： T ( n )= O(f(n))。它表示随問題規模 n 的增大， 算法執行時間的增長率和f ( n ) 的增長率相同， 稱作算法的漸近時間複雜度， 簡稱為時間複雜度。 其中 f ( n ) 是問題規模 n 的某個函數。
用大寫的O()來表示時間複雜度，稱之為大O表示法。
圖八：大O表示法
順序結構的時間複雜度。
例如下面這個算法：
int sum=0,n=100; //執行1次
sum=sum+n/2; //執行1次
System.out.println(sum); //執行1次 這個算法的運作次數函數是 f (n) =3。 執行次數不會随着n的變化而增大，是以這個算法的時間複雜度為 O(1)。
除了順序結構，對于分支結構而言， 無論是真， 還是假， 執行的次數都是恒定的， 不會随着 n 的變大而發生變化 ， 是以單純的分支結構 （ 不包含在循環結構中） ， 其時間複雜度也是O(1)。
線性階的循環結構會複雜很多。 要确定某個算法的階次， 我們常常需要确定某個特定語句或某個語句集運作的次數。 是以， 我們要分析算法的複雜度， 關鍵就是要分析循環結構的運作情況。
for(int i=0;i<n;i++){
//時間複雜度為O(1)的運算
System.out.println(n);
} 上面這個算法的時間複雜度為O(n)，因為算法要執行n次。
看一下下面這個算法，乍一看時間複雜度是O(n)。
int n=10;
int count=1;
while (count<n){
count=count*2;
//時間複雜度為O(1)的運算
System.out.println(count);
} 每次 count 乘以 2 之後， 就距離n更近了一分。 也就是說， 經過log2^n次之後退出循環，是以這個循環的時間複雜度為O(logn)。
看一下下面這個雙循環，把 O(n) 的代碼再嵌套循環一遍。它的執行次數是m*n，時間複雜度是O(n²)。
for (int i=0;i<n;i++){
for (int j=0;i<m;j++){
//時間複雜度為O(1)的操作
System.out.println(i*j);
}
} 在平方階上擴充，立方階O(n³)、K次方階O(n^k)，也都很好了解，3層循環，k層循環。
空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢，我們用 S(n) 來定義。
S(n)= O(f(n))
一般情況下， 一個程式在機器上執行時， 除了需要存儲程式本身的指令、 常數、變量和輸入資料外， 還需要存儲對資料操作的存儲單元。 若輸入資料所占空間隻取決于問題本身， 和算法無關， 這樣隻需要分析該算法在實作時所需的輔助單元即可。 若算法執行時所需的輔助空間相對于輸入資料S而言是個常數， 則稱此算法為原地工作， 空間複雜度為 O(1)。
通常， 我們都使用 “時間複雜度” 來指運作時間的需求， 使用 “空間複雜度” 指空間需求。 當不用限定詞地使用 “複雜度” 時， 通常都是指時間複雜度。