簡單的演算法筆記 – 第一集

程式資結演算法

Written by:

我們可能一天到晚聽到:FB 又改了它的演算法啦~ 這個技術背後的演算法邏輯是Blahblah阿~

一直演算法演算法,聽起來好像很厲害… 但它到底是什麼意思呢?!是一種技術嗎?是一種數學嗎?到底演算法又和程式有什麼差異呢?

今天就要來帶大家看看什麼是演算法(Algorithm),在本文內甚至可以教大家針對一個問題、寫出相對應的演算法,在未來看到這個詞別再害怕噢~

 

什麼是演算法?

演算法是用以解決特定問題的有限個步驟和敘述

在電腦尚未問世以前,演算法就是數學家極為重要的研究主題。現在也是電腦科學中非常重要的基礎科目。

演算法並非程式語言,而是一種思考流程。程式語言代表的則是符合該語言的文法規則;所以我們可以先把解決問題的流程寫下來、再把這個程式碼轉換成相應的程式語言。

比如相同的問題和解決流程、程式碼可以寫成 C/C++、Python、Java…。

也就是說,我們會先有演算法,再把演算法轉換成程式。

 

一般來說,演算法須滿足下列五個標準:

1. 輸入(Input):輸入的資料量至少(大於等於) 0 個。

2. 輸出(Output):輸出的結果至少(大於等於)1 個。

3. 明確性(Definiteness):演算法中的每一個敘述都必須是明確的定義。

註:比如「天氣冷的時候穿上外套」,就不具備明確性。因為每個人對於天氣冷會有不同的看法。「天氣溫度為攝氏 10 度的時候穿上外套」就具備明確性。

4. 有限性(Finiteness):演算法必須在執行有限個步驟後能夠終止。也就是說不能無限期的執行。

註:但程式(Program)不一定要滿足有限個。

(1) 比如 infinite loop recursion(無限遞迴的程式)。雖然你的電腦會一直跑一直跑跑到爆炸、永遠不會停,但這個程式還是可以跑噢!

 

(2) 為了實際上的必要:

作業系統在不關機的情況下要能不斷的跑;或是保全系統亦然(可以說這個保全系統程式跑一遍就夠了嗎ˊ__>ˋ)。

5. 有效性(Effectiveness):演算法中的每個敘述必須是夠基本,可讓人用紙和筆即可追蹤。這是一個操作型的定義。

註:如果要解決一個問題,要先想好問題、再去找一個程式語言把它寫下來的話,會很沒有效率。

比如說程式真正在跑的時候不work,我們要怎麼知道到底是解法有問題,還是轉換成程式的時候寫錯,還是Compile的時候出錯?可能有問題的地方太多,還要花時間寫好程式才能對答案的話也太過耗時。

第五點的重點是要驗證「問題解法的有效性」。不用考慮效能和程式語言的語法,只要用紙筆即能 trace 完演算法、確定問題能解。工程師在寫程式的時候就能更快地確定是哪邊出了差錯。

不過另外要注意的是,正確性(Correctness)並不在演算法的五個標準之內。因為我們的「有效性」標準是要「可操作」,就是能用紙筆Run一次。就算演算法出了差錯、那也還叫演算法。

 

如何想出並表達一個演算法?

演算法最大的挑戰,在於如何想出問題的解法。瞭解演算法也就是瞭解問題如何被解決的過程。

想出演算法的能力不見得可以透過學習提升,很多時候會需要像藝術創作一樣的靈感…ˊ__>ˋ。要想出好的演算法,大致上的流程是:

1. 分析問題(有無輸入資料?條件限制?)

2. 想出解決問題的辦法(雖然這看起來有點廢話,不過主要是去思考:有沒有類似問題已經有解法?如果還想不到,可以縮小問題的範圍,看看到什麼程度可以想出解法,再擴大它。)

3. 擬定演算法的步驟、再轉換成相對應的程式。

4. 評估該演算法是否具備能用來解決其他類似問題的潛力。

螢幕快照 2017-04-16 03.55.58.png

要構思出演算法,我們可以運用一些容易理解的方式,將思考流程表達出來。其實就是把你自己當作一台電腦,想想看你會如何依序解決一個問題呢?

讓我們舉個例子好了,比如:找出 {23, 5, 33, 7, 82} 這幾個數字中的最大值。如果你是電腦,會怎麼做呢?

你可能會這麼做:

  1. 先將最大值的初始值設為 0 。
  2. 如果最大值和 23 比較、發現 23 大,就把 23 設為最大值。(此時最大值被改成 23)
  3. 如果最大值和 5 比較、發現 5 大,就把 5 設為最大值。(此時最大值仍為 23)
  4. 如果最大值和 33 比較、發現 33 大,就把 33 設為最大值。(此時最大值為 33)
  5. 如果最大值和 7 比較、發現 7 大,就把 7 設為最大值。(此時最大值仍為 33)
  6. 如果最大值和 82 比較、發現 82 大,就把 82 設為最大值。(此時最大值為 82)
  7. 將最大值的結果印出來。

哇!事實上你已經寫完一個演算法了呢!

如果將上面的過程用程式語言(範例為 C 語言)寫下來,就會是:

 

當然,用這種做法的缺點就是程式沒有擴充性——如果改變要比較的數值、或數值的個數,整個程式就必須重寫。

所以根據相同的演算法,我們可以換一種程式的寫法:

 

一旦要比較的數值或個數被改變,只要改掉第 3 行的陣列大小和元素、並將第 5 行的 i 改成新的個數即可。相較前一個程式、如此寫法更具備擴充性。

然而注意到了嗎,我們解決問題的方法其實是一樣的!只是程式的寫法不同了而已。也就是說在演算法的階段,只是要「想出解決問題的流程」而已。

 

演算法的常見表達的方式,包括了「流程圖」(Flowchart)或「虛擬碼」(Pseudocode)。

判斷.jpeg

上述即為使用流程圖,來判斷兩個數字為奇數或偶數的演算法。

 

另一種更常見的表達方式是虛擬碼(Pseudocode)。通常是一般的口語敘述,來描述問題的解法。這樣的虛擬碼並不能實際作為一個程式跑起來。

像是我們在上面一步步寫下來「比大小」解決問題流程,就是一個虛擬碼噢!

當然讀者可能會發現,如果不是用程式碼、而是用描述的方式寫下來,那寫法就可以有很多種呀!

像是如果我想把它寫成更接近程式碼的樣貌,就可以寫成:

 

這樣也是一個演算法的虛擬碼噢!虛擬碼並不是真的要在電腦上執行,所以只要能看得懂就行了、沒有什麼語法要遵守。

你可以把「 a 這個變數的值是 5 」的這句話寫成:

  • a = 5; (把 5 這個值 assign 給 a)
  • a <- 5; (把 a 的值設定為 5)
  • a is 5;

也由於沒有固定的語法,因此大部分人傾向採用將來想要撰寫程式的程式語言(比如這個問題之後打算要用 C 還是 Python 解),來作為虛擬碼。

那既然同一個解決流程、可以有不同種演算法的寫法,那到底要怎麼知道哪一種方法比較好呢?這就牽涉到效能分析的問題啦!

 

演算法的效能分析

既然針對同一個問題所撰寫的演算法有許多種,要判斷優劣、我們會依據下列兩方面來分析:

1. 空間複雜度(Space Complexity):執行完畢所需的記憶體空間。

2. 時間複雜度(Time Complexity):執行完畢所需的時間。

其中,時間複雜度又比空間複雜度更重要。一來是因為現在的儲存空間很便宜;二來是資料量變大時,空間複雜度的差異通常不大、但時間複雜度則會有極大的差異。

所以一般來說,我們會專注於討論時間複雜度。

再進一步來說,由於多數程式還有編譯、運行環境的差異,因此我們通常會討論演算法的時間複雜度時,而非程式。

那我們要如何測量執行時間呢?通常是計算每執行一次有幾個步驟(Steps per Execution)。也就是統計演算法中、要執行步驟的次數加總。

這種測量結果和電腦的執行速度沒關係,但和輸入(Input)、輸出(Output)資料量習習相關。如果想要計算的資料越多,時間複雜度也就越高。

 

比如下列程式【計算 n 個數的總和】的步驟數如下:

  • S/E (Steps per Execution):該敘述每執行一次、需要花費多少個步驟
  • 頻率 (Frequency):該敘述的執行次數。
  • 程式的步驟數 (Total):S/E * 頻率。

 

把 Total 加起來:1 + 3(n+1) + n + 1 = 4n+5,即這個演算法的時間需求。

 

其實對於電腦來說,由於電腦的執行速度很快,所以對於時間複雜度的係數和常數(比如 4n+5 的 4 和 5)在資料量很大很大的時候,都可以省略,只針對次方的部份討論。

也就是將 4n+5 、300n+1234 等,全都視為與 n 相同的線性關係。但 4n² + 5,則視為 n²。

也就是說,我們在意的是時間複雜度的成長速度(Growth Rate)是線性成長、還是指數型成長。

linear

不知道大家有沒有聽過一個故事——有個大臣因功向國王邀賞,獎賞內容是要求國王將第一個棋盤格子中擺 1 粒稻米、第二個棋盤格子中擺 2 粒稻米、第三個格子中擺 4 粒… 以此類推到 101 個格子。

國王表示:安安,這個要求太容易了!差點就要答應下來,直到被身邊的一位智者阻止。答案會變成 2 的 100 次方,也就是 2676506 * 10 的 30 次方的驚人天文數字。挖空全國的稻米都不知道給不給得出來。

由此可知,線性成長、和指數型成長的速度差異,是非常巨大的!所以我們要尋求一種方法,來描述執行時間相對於問題大小的成長速度

這種方法,就是規範出理論的上限值–– 符號表達為「O」,唸作 Big-Oh。

理論上,這支演算法的成長速度會小於這個上限值,也就是說在最差的情況下,表現也不會比 O( )差。比如【計算 n 個數的總和】的時間複雜度即 O(4n+5) = O(n)。

舉例來說,若有兩支功能相同的演算法(都能解決同樣一個問題),但時間複雜度卻分別為 O(n) 與 O(n²)。現在讓它們各自在一部每秒鐘能執行 100 個指令的電腦上、處理 100 萬筆資料,各需花費多少時間呢?

答案是:O(n) 只需 1 秒鐘,然而 O(n²)  則需要 100 萬秒。因此若是一個演算法的時間複雜度高達 O(n²) 時,通常都會想辦法縮減。

 

演算法是一門能夠動動腦的有趣科目,也是要解決很實際的問題。未來將會陸續出接下來的幾集給初學者,歡迎大家繼續收看噢!

(不過還是建議要有一些程式基礎再來看~若沒學過程式的讀者看完這篇就可以了,之後請先存起來吧XDD)

 

13 Replies to “簡單的演算法筆記 – 第一集”

  1. 訪客 說:

    這篇寫得非常淺顯易懂,真的是篇好文章!!

  2. 簡士凱 說:

    寫的相當淺顯易懂,一篇淺談演算法的好文章

  3. 陳冠君 說:

    我最近也在研究演算法xdd

  4. 訪客 說:

    懂程式的女生很迷人

  5. 路人甲 說:

    範例 O(n) v.s. O(n^2) 的答案看不懂,能否請站主解說一下計算過程,感謝

    • Lynn 說:

      這個舉例有點爛,近日應該會再把它改掉~到時候再通知你來看><

      • tom 說:

        你好,我想應該是你少了一個字,就是一部電腦一秒鐘可以處理100萬個指令,你打成100個指令,我想是這樣,計算上就會變得有點奇怪,還是真的是100個指令?

  6. Will_NCKU 說:

    您好,”什麼是演算法?”那個部分裡的”再把這個程式碼轉換成相應的程式語言。”這句話,
    我覺得這裡”程式碼”這個詞的使用比較不精確,說是”虛擬碼(pseudo code)”比較精確一些。
    如果說是”程式碼”表示已經使用程式語言來表述了。

    演算法的表示方式有文字、流程圖、虛擬碼等等。虛擬碼這種表示滿常在書上看到的。

    若是改成”再把這些[描述文字/流程/虛擬碼]轉換成相應的程式語言。”,
    或者”再把這些[描述文字/流程/虛擬碼]經由程式語言轉換成相應的程式碼。”可能精確一些。

    這只是我個人的認知/淺見,不見得對,不過多少可以參考一下。

    BTW,非常感謝您願意花時間寫些科普文章,我覺得這是目前台灣缺乏的。

    • Will_NCKU 說:

      Sorry,我看到前面就留言了,留言完繼續看下去才發現你有提到虛擬碼和流程圖,不好意思…

  7. 張皓雨 說:

    你的寫法相當淺顯易懂,棒。

  8. 小書童 說:

    安安,你好

    請問演算法的正確性如何保證呢? 用數學證明? 還是測試呢?

  9. 小抹 說:

    範例 O(n) v.s. O(n^2) 的答案看不懂+1 卡個位等解答QQ

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *