《資料結構》學習筆記二：算法（一）

本節雖然名為“算法”，其實講的隻是算法的一些概念以及評估方式，并沒有涉及很複雜的算法。

解決問題：

1. 什麼是算法
2. 算法的特性
3. 算法設計的要求
4. 如何評估一個算法的優劣

通過本節的學習，我們可以輕松的解決這些問題。

1.算法的概念

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

通俗的講，算法就是解決問題的步驟。很多優秀的算法都是前人不斷的總結，積累下來的求解特定問題的步驟。

我們在上一節中提到了

程式設計 = 資料結構 + 算法

那麼算法與資料結構的關系就像梁山伯與祝英台，羅密歐與朱麗葉。資料結構和算法可以單獨列出來講解，但是把他們放在一起才會感受到前人的智慧。

2. 兩種簡單算法的比較

為了更加直覺的感受到什麼是算法，我們來舉一個小例子。

問題：

計算 1+2+3+......+100 的和。

有些朋友該說了，這不是太簡單了嗎，不管使用哪種語言，都會很容易的想到這種簡單的寫法，在編譯器立馬寫下如下代碼：

(這裡使用swift語言)

// 計算1到100的和
var sum = 0, n = 100
for i in 1...n {
    sum += i
}
print("sum = \(sum)")
           

很容易看明白吧。這其實也是一種算法，他就是一種解決求和問題的算法，至于優劣，我們後來再讨論。

我們這裡插述一個大數學家高斯的故事。

高斯小時候，又一次老師出了一個題目，讓同學們計算 1到100的和，就是上面我們解決的那個問題。高斯很快就計算出了結果，他是如何快速計算出結果的呢？

sum = 1 + 2 + 3 + ......+100

sum = 100 + 99 + 98 + ......+ 1

sum + sum = 101 + 101 + 101 + ......+101

共有 100個101 。

是以，

sum = (1 + n) * n / 2

上述的算法改進之後就變成了：

// 優化
var sum2 = 0, n2 = 100
sum2 = (1 + n2) * n2 / 2
print(sum2)
           

這樣計算是不是快了很多？

3. 算法的特性

算法具有五個特性：

輸入、輸出、有窮性、可行性、确定性。

輸入：

算法具有0個或者多個輸入。

輸出：

算法至少有一個輸出。

有窮性：

算法必須會自動結束并且在可接受的時間範圍内。

可行性：

算法的每一個步驟都是可行的，每一步都通過執行有限次數完成。

确定性：

相同的輸入，隻有唯一的輸出結果。

4. 算法的設計要求

正确性、可讀性、健壯性、時間效率高、存儲量小。

正确性：

算法必須是正确的，能夠解決問題，得到問題的正确答案。

可讀性：

算法應該是便于閱讀交流和了解的。

健壯性：

對于異常情況，都要有很好的相容性。

時間效率高：

執行時間越短的算法越好。

存儲量低：

占用記憶體越小的越好。

5. 算法效率的度量方法（時間複雜度）

算法的效率度量有兩種方式：

1. 事後統計方法
2. 事前分析估算方法

事後統計方法：

通過設計好的測試程式和資料，利用計算機計時器對不同的算法運作時間進行比較，進而确定效率的高低。

這是一種很不精确的度量方式，誤差會很大。

為什麼？

因為這樣的話，需要事前編制測試程式，花費大量的精力，如果算法不好，則又是白費力氣。且時間的計算依賴計算機的硬體以及軟體，計算機的軟硬體是有差别的，而且運作不同的程式也會導緻結果的不同。

這是一種很科學的計算方式。

它是在計算機程式編制之前，依據統計方法對算法進行估算。

程式在計算機上運作所消耗的時間取決于以下的因素：

1.算法的政策（算法好壞的根本）

2.編譯産生的代碼量（編譯器決定）

3.問題的輸入規模

4.機器執行指令的速度（硬體性能）

是以，一個程式的運作時間，依賴于算法的好壞和問題的輸入規模。

我們還來看之前的求和的例子：

var sum = 0, n = 100 ……執行 1 次

for i in 1...n { …..…………執行 n + 1次

sum += i ……... …………執行 n 次

}

print("sum = (sum)") ……執行 1 次

執行次數是

1 + （n +1） + n + 1 = 2n + 3 （次）

第二種算法

var sum2 = 0, n2 = 100 ············執行1次

sum2 = (1 + n2) * n2 / 2············執行1次

print(sum2)····························執行1次

1 + 1+ 1 = 3 （次）

顯而易見，那種算法效率更高。

測定運作時間最可靠的方法就是計算運作時間有消耗的基本操作的執行次數，運作時間與整個次數成正比。

時間有限，本節暫時記錄這些内容，下一篇文章中我們一起學習算法中函數的漸進增長、算法的時間複雜度、算法的空間複雜度等内容。

一起加油吧。