250
大話數據結構之二：算法
1.數據結構和算法的關係
個人感覺程序=算法+數據結構。數據結構是算法實現的基礎，算法總是要依賴於某種數據結構來實現的。往往是在發展一種算法的時候，構建了適合於這種算法的數據結構。當然數據結構和算法也有區別：數據結構關注的是數據的邏輯結構、存儲結構以及基本操作，而算法更多的是關注如何在數據結構的基礎上解決實際問題。算法是編程的思想，數據結構則是這些思想的邏輯基礎。
2.算法定義
算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，並且每條指令表示一個或多個操作。
現實世界中的問題千奇百怪，算法也隨著千變萬化，沒有通用的算法可以解決所有的問題。
3.算法特性
3.1輸入
算法要具有零個或多個輸入
3.2輸出
算法至少有一個或多個輸出
3.3有窮性
算法在執行有限的步驟之後，自動結束而不會出現無限循環，並且每一個步驟在可接受的時間內完成。
3.4確定性
算法的每一個步驟都有確定的含義，不會出現二義性。
3.5可行性
算法的每一步都必須是可行的，也就是說，每一步都能通過執行有限次數完成。
4.算法設計要求
4.1正確性
算法的正確性之算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求，能夠得到問題的正確答案。
這裏的正確分為四個層次：
1. 算法程序沒有語法錯誤。
2. 算法程序對合法的輸入數據能夠產生滿足要求的輸出結果。
3. 算法程序對非法的輸入數據能夠得出滿足規格說明的結果。
4. 算法程序對於精心選擇的，甚至刁難的測試數據都有滿足要求的輸出結果。
4.2可讀性
設計出來的算法還要便於閱讀、理解和交流。
4.3健壯性
當輸入數據不合法時，算法也能做出相關處理，而不是產生異常或莫名其妙的結果。
4.4較低的時間複雜度和空間複雜度
5.算法效率的度量方法
5.1事後統計方法
通過設計好的測試程序和數據，利用計算機計時器對不同算法編製的程序的運行時間進行比較，從而確定算法效率的高低。
這種方法有很大的缺陷：
1. 必須依據算法實現編製好程序，這通常需要花費大量的時間和精力。如果編製出來的算法很糟糕達不到要求，就是竹籃打水一場空。
2. 算法的執行時間依賴計算機硬件和軟件等環境因素，有時會掩蓋算法本身的優劣。
3. 算法的測試數據設計困難，並且程序的運行時間往往與測試數據的規模有很大的關係，效率高的算法在小的測試數據麵前得不到體現。
5.2事前分析估算法
在編寫程序前，依據統計方法對算法進行估算。
一個用高級語言編寫的程序在計算機上運行時所消耗的時間取決於下列因素：
1. 算法采用的策略、方法；
2. 編譯產生的代碼質量；
3. 問題的輸入規模；
4. 機器執行指令的速度。
6.函數的漸進增長
給定兩個函數f(n)和g(n)，如果存在一個整數N，是的對於所有的n>N, f(n)總是比g(n)大，那麼我們說f(n)的增長漸進快於g(n).
判斷一個算法效率時，函數中的常熟和其他次要項常常可以忽略，而更應該關注主項。
7.算法時間複雜度
在進行算法分析時，語句總的執行次數T(n)是關於問題規模n的函數，進而分析T(n)隨n的變化情況並確定T(n)的數量級。算法的時間複雜度，也就是算法的度量，記作：T(n)=O(f(n)).它表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，乘坐算法的漸進時間複雜度，簡稱為時間複雜度。其中f(n)是問題規模n的某個函數。
推導大O階的方法：
1. 用常熟1取代運行時間中的所有加法常數。
2. 在修改後的運行次數函數中，隻保留最高階項。
3. 如果最高階項存在且不是1，則去除與這個項相乘的常數。
得到的結果就是大O階。
算法的時間複雜度分為以下幾種情況：
7.1常數階
7.2線性階
7.3對數階
7.4平方階
8.算法空間複雜度
算法的空間複雜度通過計算算法所需的存儲空間實現，算法空間複雜度的計算公式記作：S(n) = O(f(n)),其中，n為問題的規模，f(n)為語句關於n所占存儲空間的函數。
在設計算法時，常用的一個技巧就是空間換時間。
最後更新：2017-04-03 18:52:12