Algorithm

演算法是什麼?

演算法是計算機科學非常重要的基礎科目。簡單來說,演算法就是用電腦算數學的學問(古代人用算盤算、現代人用電腦算),可以說是數學科目。

想要解決現實生活當中的各種問題,計算機科學家就把現實問題對應到數學問題,然後設計公式、把公式寫成程式,讓電腦執行程式計算答案──這些公式就叫做演算法了。

儘管這裡用了「公式」這個字眼來形容演算法,然而並不是各位印象中的數學公式。由於電腦能夠執行繁複的計算,所以公式可以設計成好幾十行、好幾百行,甚至用到很多數學理論。

因此呢,就算學習過演算法的人,也不見得懂得設計演算法;因為數學、程式的東西實在太複雜了。想把現實問題對應到數學問題,那就更複雜了。

電腦只會算數字

回過頭來,電腦又是什麼?電腦是個很潮的中文翻譯,不過實際上電腦的原意是「計算機」。電腦的英文叫做computer,而計算的英文就叫做compute。

電腦是一臺計算機,只會計算、判斷、儲存數字。又快又準。

程式是一連串計算、判斷、儲存數字的步驟。

電腦只會處理數字(二進位數字)。電腦裡的每一個文字、每一種顏色、每一種聲音,其實都有相對應的數字。

打個比方,我們規定:用1代表「一」,用2代表「乙」,用3代表「人」,……。一個數字對應一個中文字。電腦裡面的所有中文字,都依循人為規定,變作了數字。

再打個比方,「人」這個字,呈現電腦螢幕上是個「人」樣。電腦螢幕的畫面,是由許多小光點組成的;電腦螢幕上的「人」也是由許多小光點組成的。我們以「人」的左下角為座標原點,橫向為X軸,直向為Y軸,那麼「人」其實是(0,1)、(1,2)、(2,3)、...這些座標畫上黑點後所形成的。「人」這個字的的形狀,在電腦中變作了一連串的數字。

同樣的道理,呈現在電腦螢幕畫面上的文字、顏色、圖片、影像、聲音,全部都可以化作數字。一切事物在電腦裡面都是數字。

電腦並沒有想像中的那麼神奇。不過電腦最厲害的地方並不是電腦本身,而是在於電腦可以接上各式各樣的設備。接上攝影機與螢幕,就可以把色彩變成數字、把數字變成色彩;接上麥克風與耳機,就可以把聲音變成數字、把數字變成聲音。

電腦一旦接上了設備,就額外有用處。接上話機和基地台,就可以互通有無;接上數位相機和印表機,就可以製造回憶;接上重量儀和篩子,電腦也會揀土豆;接上車廂、接上警示燈、再雜七雜八接上一堆東西,就變成了大眾運輸系統。

若要用電腦解決現實問題,通常要考慮兩個方面:一、電腦應該接上那些設備?如何用電腦控制這些設備?二、現實問題如何對應到數學問題?如何設計演算法?

程式用來比對數字、改變數字、儲存數字

舉個例子,我們希望把螢幕上的「人」變成斜體字。過程大略是這樣──首先呢,把「人」的形狀(0,1)、(1,2)、(2,3)、...這些數字拿出來;然後呢,位置越高的座標,就往右移動多一點,如此一來就成為斜體字了。想讓座標往右移動,就是讓電腦做數字加法計算,然後把相加結果儲存起來。

再舉個例子,用滑鼠點選一個資料夾,資料夾的顏色會反白。過程大略是這樣──首先呢,電腦偵測到滑鼠點擊的座標之後,把座標轉換成數字;然後呢,再把螢幕畫面的資料拿出來,看看螢幕上每個東西的座標,是哪一個與滑鼠的座標相符合;噢,原來是一個資料夾的圖示,把資料夾的顯示顏色給反白過來。

再舉個例子,電腦據說會揀選土豆。過程大略是這樣──把每一顆土豆拿出來,利用特殊的儀器,把形狀、重量、色澤、氣味統統轉換成數字,儲存在電腦裡面;然後呢,用電腦比較這些數字,找出優良的土豆,如此一來就有綿綿鬆鬆的土豆了!

編寫程式,計算數字,這就是程式設計師的工作。

數學和程式這麼複雜,為什麼要用電腦解決現實問題?

電腦的計算速度可說是非常的快,一秒鐘可以進行好幾千萬次。就算文字多麼的多,圖片多麼的大,電腦處理起來,也是輕鬆寫意,順暢無比。

打開電腦裡的任何一份文件,用滑鼠捲動一下文件畫面,眼睛都還沒眨一下,正確畫面馬上就呈現在螢幕上了。事實上在捲動畫面的時候,電腦已經經過幾千萬次的計算,僅使用了極短的時間,就把螢幕上應該呈現的資料全部計算好了。

人類會想要用電腦解決問題,正是仰賴電腦的計算速度、正確性,以及電腦會自動按照程式計算的特性。程式設計師只要花心思寫出一支好程式,接下來的工作就可以讓電腦代勞了。電腦做的比人類更快更好,電腦做得到人類做不到的事情;儘管數學和程式很複雜,還是有很多人選擇使用電腦解決問題。

那些現實問題是用演算法解決的?

現代人的生活已經離不開演算法了。比如說你的手機裡面就有上百個演算法。你可以Google一下新聞。本站首頁底部的Multimedia和Interdisciplinarity欄位,也收集了許多影片。

Algorithm

演算法是什麼?

演算法由三個部分組成:輸入、計算步驟、輸出。介紹這件事情的時候,有人連結到函數的概念,也有人連結到黑箱白箱的概念。

          -----------------
input --->| computational |
          | sequence      |---> output
          -----------------

輸入、輸出是一堆數字。實務上是將這些數字放在資料結構,例如array、list。輸入來源,通常是硬碟裡面儲存的檔案,或者是藉由硬體裝置擷取到的數字,例如數位相機、麥克風等等。輸出去處,通常是硬碟裡面儲存的檔案,或者是藉由硬體裝置轉換之後以其他型態呈現,例如數位電視、數位音響等等。

計算步驟是一連串處理數字的指令。指令有兩種類型,一類是運算,例如數學運算加減乘除、邏輯運算且或非、比較運算大於等於小於、位元運算左右反且或異或。另一類是讀寫,例如讀取某處的數字、儲存數字至某處,就跟計算機的MR、M+按鍵的意義相似。

古人定義演算法,規定計算步驟的數量是必須是有限步,不是無限步。用程式語言的術語來說就是:演算法不能有無窮迴圈。

古人當初規定有限步,是為了方便統計總步數。但是實務上,很多電腦程式是開啟之後就保持執行狀態,直到當機、重開機,例如網路傳輸的演算法。因此實務上可以是無限步。

如何記載一個演算法?

有人用虛擬碼來記載一個演算法。如要設計電腦程式,虛擬碼是比較恰當的。

GREATEST_COMMON_DIVISOR(a, b)
1   while a ≠ b do
2       if a > b then
3           a ← a - b
4       else
5           b ← b - a
6   return a

有人用流程圖來記載一個演算法。如要設計電子電路,流程圖是比較恰當的。

大多數時候,我們無法光從虛擬碼和流程圖徹底理解演算法,就如同我們無法光從數學公式徹底理解數學概念。想要理解演算法,通常還是得藉由文字、圖片的輔助說明。

如何實作一個演算法?

實作的意思是:實際去操作、實際去運行。

對於資工系學生來說,自然就是把演算法撰寫成電腦程式,例如C或者C++程式,然後在個人電腦上面執行程式。

對於電機系學生來說,自然就是把演算法設計成電子電路,在麵包板印刷電路板PLD上面執行。

電子電路也有加法器、減法器、AND邏輯閘、OR邏輯閘等等,所以也可以用電子電路實作演算法。例如電子錶、隨身聽、悠遊卡等等,都是直接將演算法做死在晶片上面。在個人電腦、智慧型手機還沒流行之前,以往都是用電子電路實作演算法。

電子電路的執行速度是飛快的,電腦程式的執行速度慢了一點。然而,製作電子電路的過程相當麻煩,需要精密的設備、複雜的製程、大量的人力和經費,而且製成之後就無法修改;相對地,寫程式就簡單輕鬆多了,在電腦上面很容易調整程式碼,又可以儲存很多程式碼,最主要的是家家戶戶都有電腦。

時間複雜度、空間複雜度

要評斷一個演算法的好壞,最基本的指標是時間和空間。

最直覺的方式,就是測量程式的執行時間、程式的記憶體使用量。但是由於相同演算法於不同電腦的執行時間會有差異,又由於每個人實作演算法所採用的程式語言、程式設計技巧都不一樣,所以執行時間、記憶體使用量不是一個穩定的評斷標準。

數學家於是計算步驟數量。

BUBBLESORT(A, n)                  | steps   
1 for i ← 0 to n-1 do             | n       
2     for j ← i to n-i-1 do       | n(n-1)/2
3         if A[j] < A[j+1] then   | n(n-1)/2
4             temp ← A[j]         | n(n-1)/2
5             A[j] ← A[j+1]       | n(n-1)/2
6             A[j+1] ← temp       | n(n-1)/2
total = n + 5n(n-1)/2
      = n + 2.5n² - 2.5n
      = 2.5n² - 1.5n
      = O(n²)

數學家把步驟數量寫成代數式子。例如當輸入資料有n = 1000個數字,步驟數量一共是2.5×1000² - 1.5×1000 = 2498500步。

有了步驟數量之後,還可以進一步粗估執行時間。假設一個步驟需要10個clock,而電腦中央處理器CPU的時脈是2GHz:每秒鐘執行2000000個clock,那麼程式執行時間大約12.4925秒。

但是這不是精準的步驟數量。由於實作的關係,係數很容易變動,所以係數的意義不大。因此數學家只取出代數式子的最高次方,並且規定n必須足夠大(類似微積分的趨近無限大)。儘管這是非常不精準的估算方式,不過還是可以對常見的演算法進行簡易分類,粗略地比較快慢。

               | time*       | space
---------------+-------------+--------
bubble sort    | O(n²)       | O(n)
insertion sort | O(n²)       | O(n)
merge sort     | O(n log(n)) | O(n)
quicksort      | O(n²)       | O(n)
heapsort       | O(n log(n)) | O(n)
counting sort  | O(n+r)      | O(n+r)

*worst case

空間的計算方式與時間類似,就不多提了。

解決問題的成效

要評斷一個演算法的好壞,除了時間和空間的用量以外,主要還是看演算法解決問題的成效如何。

數學問題,通常可以明定解答好壞,例如數字越大越好。通常這種情況,有多種演算法可以求得正解,那麼這些演算法的成效是一樣好的。

真實世界的問題,通常難以界定絕對的好壞優劣,例如美醜、樂音噪音、喜怒哀樂、是非對錯等等,此時演算法的成效,則由人類自行判斷,利用兩兩比較、投票表決等等方式來決定成效。

數學與計算學

數學是以基本元件來構築事物、表達概念。而數學家藉由數,嘗試構築每一件事物、表達每一個概念,拼湊出世界的全貌。比如位置、形狀、關係、轉換、遞迴、極限、比較、排列、正反、假設,這些東西都是數。又比如有、無、聚、散、疏、密、盈、虧、彎、直、交、錯、動、靜,這些東西也都是數。與物體的行為有關的數,就是物理;與物質性質變化有關的數,就是化學;與生命運作有關的數,就是生物學。繼續細分下去的話,我們所知的各種東西,其實皆可說是數。

在數當中,可以用數量來表示的,便可以計量。像是情緒、風格、謀略,難以用數量來表示,也就難以計量,甚至不可計量。像是動作、旋律、次序,可以部分地或完全地用數量表示,便得以計量。計算學是以數量來構築事物、表達概念。而計算學家藉由數量,嘗試量度各種事物、各種概念,掌握其確切的程度與層次。

Algorithm

學習程式語言

學習程式語言,有兩個層次:一、程式語言本身的語法;二、把想法轉換成程式碼。

第一個層次稱做「程式語言Programming Language」。目標是背熟規格書、靈活運用程式語言。

第二個層次稱做「程式設計Programming」。目標是設計程式碼解決問題。然而現今世界上還沒有一套公認的、固定的學習流程。

學習演算法

學習演算法,有兩個層次:一、演算法本身的運作過程;二、把想法轉換成演算法。

第一個層次稱做「演算法Algorithm」。目標是理解演算法、靈活運用演算法。讀者可以參考本站首頁的各大欄位,例如圖論、計算幾何、字串學等等。

第二個層次稱做「演算法設計Algorithm Design」。目標是設計計算步驟解決問題。讀者可以參考本站首頁的Algorithm Design欄位,以及從各種演算法當中汲取經驗、擷取靈感。

學習函式庫、工具

很多現實問題及其計算步驟,已經成為標準流程,沒有什麼改動的餘地,成為了演算法。因此科學家就把這些演算法編寫成「函式庫Library」,再把現實生活的常見需求編寫成「工具Toolkit」,讓程式設計的過程更加迅速。網路上已經有許多現成的函式庫和工具,通常也附帶詳細的使用說明書,方便工程師運用。

現今的軟體產業當中,幾乎都是直接使用現成的函式庫、工具;只有從事創新研發,才會從無到有設計程式碼、設計演算法。優秀的工程師,總是善於活用函式庫、工具,快速實現自己想要的功能。

演算法書籍

教科書:適合資工系學生。

Algorithms
Robert Sedgewick and Kevin Wayne

Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Introduction to Algorithms: A Creative Approach
Udi Manber

Algorithm Design
Jon Kleinberg and Éva Tardos

Algorithm Design: Foundations, Analysis, and Internet Examples
Michael T. Goodrich and Roberto Tamassia

An Introduction to the Analysis of Algorithms
Robert Sedgewick and Philippe Flajolet

An Introduction to the Analysis of Algorithms
Michael Soltys

工具書:適合程式設計師。

Algorithms in a Nutshell: A Practical Guide
Gary Pollice, Stanley Selkow, George Heineman

The Algorithm Design Manual
Steven Skiena

科普書:適合小朋友和大朋友。

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
繁:《演算法圖鑑》
簡:《我的第一本算法书》

Grokking Algorithms: An illustrated guide for programmers and other curious people
繁:《寫程式前就該懂的演算法:資料分析與程式設計人員必學的邏輯思考術》
簡:《算法图解》

故事書:適合看熱鬧鄉民。

Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists
繁:《勇闖資訊新未來:打造資訊科技的幕後英雄》
简:《奇思妙想:15位计算机天才及其重大发现》

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers
繁:《改變世界的九大演算法:讓今日電腦無所不能的最強概念》
简:《改变未来的九大算法》

Automate This: How Algorithms Came to Rule Our World
繁:《演算法統治世界》
简:《算法帝国》

演算法課程

Adam Blank
演算法課程網站,有許多課程講義。

Jeff Erickson
演算法課程網站,有許多課程講義。

Erik Demaine
演算法課程網站,有許多特殊主題。

演算法網站

GeeksforGeeks
程式語言、數學、演算法益智問題。

Algorithms Notes
演算法益智問題。

Rosetta Code
各式各樣的問題的實作程式碼。

LeetCode
面試題庫,主要是演算法益智題目。可以線上練習解題。

數學網站

AMS Open Math Notes
數學家的教學筆記。

Wolfram Math World
數學百科。

The On-Line Encyclopedia of Integer Sequences
數列百科。