初學者學演算法｜談什麼是演算法和時間複雜度
程式麻瓜的程式知識課（三）
剛開始接觸程式語言學習時，我們常常會聽到身邊的資工朋友或是網路上的文章時常提到一個名詞：演算法。請教 google 大神後，維基百科給我們的答案是：
在數學和電腦科學/算學之中，算法/演算法/算則法（algorithm）為一個計算的具體步驟，常用於計算、資料處理和自動推理。精確而言，演算法是一個表示為有限長列表的有效方法。演算法應包含清晰定義的指令用於計算函式。
等等，先別吐血。你早該知道要瞭解一個硬科學的知識時，維基百科通常不會是你一開始最好的朋友。
現在，讓我們用一個簡單的關係式來表示演算法是什麼。
演算法的簡單定義
演算法的簡單定義式：輸入 + 演算法 = 輸出
演算法用最直白的方式來說，就是我輸入一個東西，想要得到另外一個東西，經過的過程就是所謂的演算法。假設我們輸入一個 2 還有一個 3，如果想要得到 6，我們需要在中間加上一個演算法「乘號 X」，讓 2 x 3 = 6。
又例如，我今天輸入一顆橘子，想要得到一杯橘子汁，中間可能經過果汁機，或是經過憤怒的手。只要最後可以順利得到橘子汁，中間的過程就可以稱為它的演算法。
複雜一點的演算法
而實際上，演算法可能複雜得多，就像假設我們今天不只要做一杯橘子汁，而是要煮一碗洋蔥燉湯，我們輸入洋蔥、油、水、鹽，想要得到洋蔥燉湯，這碗燉湯的演算法可能會類似於
1. 鍋中倒入一匙油
2. 熱油
3. 把洋蔥切末
4. 洋蔥炒至金黃色後加入一鍋水
5. 加一些鹽熬煮 10 分鐘
在日常生活中，像這樣的演算法可說是隨處可見。而在文章一開始提到，我們再接觸程式時常聽到「演算法」的這個詞，通常是指把這些步驟具體寫成程式，用來達成特定目的的過程。這些演算法簡單的可能像是把一堆數字排序，複雜的可能如大家每天用的 Facebook 所用不斷更新的 News feed 演算法。
在認識了演算法基本的定義後，接下來，就讓我們進一步來認識評斷一個演算法好壞的工具：時間複雜度 (Time Complexity)。
時間複雜度
要判斷一個演算法的好壞，最基本的兩個指標是這個演算法有多快以及他需要用到的記憶體有多少。因為時間與空間的概念大致上是互通的，我們就先來瞭解比較常見的時間複雜度。
時間複雜度是用來評斷演算法執行快慢的指標，而實務上(*註)我們通常用大 O 符號（Big O notation）來記錄時間複雜度的快慢。接下來，先讓我們用一個簡單的例子來認識什麼是大 O 符號吧！
看電影跟大 O 符號的關係
假設你今天心血來潮，想要重看經典電影名著《鐵達尼號》。你有兩個方法：(1) 走到離你家最近的租片店，租片來回需要花 25 分鐘。(2) 從網路上下載檔案，一部需要花 20 分鐘。兩者花的時間差距不大，但你可能會先選擇從網路下載。
現在，讓我們重新假設。你今天心血來潮，不只想要看《鐵達尼號》，也想要順便複習《哈利波特》全集＋《魔戒》三部曲。此時，去租片店拿到這一拖拉庫的電影還是只需要花走路的時間 25 分鐘，但從網路下載，你卻需要等電腦下載 4 個小時，這時，你可能不會選擇從網路下載。
在上面的例子中，如果選擇去租片店取得電影，所要取得的時間不受想要看的電影部數影響。也就是你的腦袋不管輸入幾個電影需求（Input），最後得到電影檔案（Output）的時間都不會因此增加。這樣的特性，用所謂大 O 符號表示這個租片演算法，我們會把演算法的時間複雜度（常以 T(n) 代表）記為 O(1)。
而如果選擇從網路上下載電影，很明顯的你輸入 n 個電影需求，拿到電影的時間就會隨著 n 成倍數成長。此時，我們會用大 O 符號把 T(n) 記為 O(n)。
看到這裡，我們可以對時間複雜度有一個最基礎的認知，也就是：
大 O 符號是用來描述一個演算法在輸入 n 個東西時，總執行時間與 n 的關係。
常見的時間複雜度比較
在設計一個程式演算法時，我們會大 O 符號比較演算法執行的效率好不好。而通常，我們會希望一個演算法至少能比 O(n²) 還要快，如果能到 O(n)、O(1) 甚至是 O(log n) 的話是最理想的情況。
從下面這張圖我們可以看到，當時間複雜度為 O(n²) 時，只要輸入的個數增加一些，它所需要花的時間就會大幅度的增加。想像一下當 n = 10,000 時，O(n²) 所需要花費的時間就會比 O(n) 的時間多一萬倍。因此，在處理大量的資料或複雜運算時，一個好的演算法設計可以省下的時間是很可觀的。
進階篇：深入時間複雜度的實際情況
到目前為止，我們認識了何謂演算法，以及評斷演算法設計好壞的工具：時間複雜度。
接下來的部分，屬於比較進階的練功，對剛接觸的新手可能會覺得有點難度或沒辦法完全理解。小小的建議是，如果你看第一次沒辦法完全體會，可以留到對程式設計更熟悉後再回頭複習。而當然，如果有任何問題也都歡迎討論！
接下來，就讓我們來看一下進階篇吧！
步驟次數
細心的讀者可能會好奇，為何上面比較圖的縱軸項目是步驟數而不是執行時間呢？
首先，我們要先來小小定義一下在程式設計中的「步驟次數」是指什麼。通常在程式碼中，每個動作只要被執行一次，我們就會說他是一個步驟，而這些動作包含印出、賦值、陣列讀取等等。
舉例來說，在程式碼中我們宣告：
x = 10賦予變數 x 數值 10 的這個動作就是一個步驟。
再舉另外一個例子：
x = 10
for i from 1 to x:
print("你好！")在 for 後面的迴圈中，輸出”你好！”這個動作被執行從 x = 1 到 x = 10 總共 10 次，因此這個 for 迴圈總共的步驟次數就是 10。但也別忘了，第一行 x = 10 也是一個步驟，所以上面的三行程式碼總共的步驟次數 = 11。
執行時間 vs 步驟次數
現在，我們瞭解了步驟次數後，我們終於可以再進一步瞭解一個重要觀念：
演算法有多快不是以秒衡量，而是以步驟次數
上面看電影的例子為了方便釐清大 O 符號跟輸入 n 的關係，我們用時間來舉例，但實際上，我們要真正衡量演算法時，是以步驟次數來看。
為何看演算法有多快不是用執行時間要幾秒呢？想像一下，美國 NASA 超級電腦需要執行 1 秒的程式，拿到我們家裡電腦執行可能需要 100 秒。而同樣的程式，用 C 語言寫跟用 Python 寫也跑的不一樣快。因為電腦效能和語言特性的都會造成影響，因此用執行時間來衡量演算法的快慢顯然不是個穩定的指標。
回過頭來使用上面看電影的例子，假設取得電影的動作我們可以用一個「只要一個步驟」的函式 get_movie( ) 替代，則「想看十部電影之走路方案」的程式碼就是單純的
// 想看十部電影之走路方案：步驟次數 = 1 次
// n = 10get_movie( )
而「想看十部電影之下載方案」的程式碼可以寫成
// 想看十部電影之下載方案：步驟次數 = 10 次
// n = 10for i from 1 to n:
get_movie()
我們從上面兩段程式碼可以觀察，所謂「步驟次數」通常會以一段程式碼中迴圈執行的次數決定（先不考慮遞迴狀況，因為這部分太複雜）。假如今天是從 1 迭代到 n 的迴圈，代表步驟次數 n。同樣的如果是一個 n 迴圈裡面再包一個 n 迴圈，代表他的步驟次數就是 n²。而如果整段程式碼都沒有用到迴圈或遞迴，則步驟次數通常以 1 表示。
實務上我們如何記錄時間複雜度
好奇的讀者可能會有疑問，那如果一個程式中有好幾個迴圈，有單純的迴圈也有雙重迴圈，這樣的步驟次數換成大 O 符號要怎麼表示呢？讓我們從下面的程式碼來瞧瞧：
for i from 1 to n:
get_movie()for i from 1 to n:
for j from 1 to n:
get_movie()for i from 1 to n:
for j from 1 to n:
get_movie()
第一段的迴圈步驟次數是 n，第二段的步驟次數是 n²，第三段的步驟次數又重複了一次 n²，所以直觀地想，這一大段的程式碼的步驟次數就是 2n² + n。
但實務上，當我們要將步驟次數轉換成以大 O 符號紀錄的時間複雜度時，有一個很重要的原則，也就是要「儘可能化簡」。
數學上，在 n 相當相當大的時候，我們在比較兩個數的大小時可以只比較他們的最高次方。因此在記錄時間複雜度時，我們同樣地會只記錄最高次方的那一項。
另外，為了方便記錄，我們也會省略所有係數，讓時間複雜度的記錄可以符合「儘可能化簡」的原則。也因此，上面有 2n² + n 個步驟的程式，我們會把它的時間複雜度簡單記成 O(n²)。
此時，也許細心的讀者會有疑問，為何 2n² + n 個步驟的程式，我們會將它的時間複雜度記的跟兩倍步驟數（ 4n² + 2n ）一樣，都是 O(n²) 呢？
這邊，我們可以把大 O 符號想像成一個區段類別，而不是一個非常非常精確的記錄單位。因此所有落在最大係數 n² 這個區段的步驟數，我們就會全部將它們歸在 O(n²) 囉！
結論
呼！終於結束看完了這篇文章，希望身為程式麻瓜的讀者還保持清醒，而有學過程式的讀者也能藉這篇文章複習一下。
如果對演算法與時間複雜度還意猶未盡，敬請鎖定 AppWorks School 的 Medium，我們在接下來的文章中會透過六個不一樣的時間複雜度，去認識在程式設計中一定要知道的六種經典演算法哦！最後，留下這篇文章的小小筆記，讓大家方便溫故知新！
溫故知新
- 演算法的簡單定義：輸入 +演算法 = 輸出
- 時間複雜度：衡量演算法執行好壞的工具
- 大 O 符號：用來描述演算法在輸入 n 個東西時，總執行時間與 n 的關係
- 在 n 非常大時，好的演算法設計可以省下非常多時間
- 演算法的速度不是以秒計算，而是以步驟次數
- 實務上，我們只會紀錄最高次方的那一項，並忽略其所有的係數
延伸閱讀
如果對程式已經有一定基礎，想要更瞭解演算法去增進程式設計的技巧的話，可以參考下面列出的這個網站，有非常非常詳盡的演算法介紹。
註：事實上，表示時間複雜度的嚴謹符號（數學上稱為漸進符號）有五個，分別是 O、Ω、Θ、o、ω。而實務上大部分指的大 O 符號 (唸作大歐)，意思其實比較相近於大 Θ (唸作 theta)，但因為方便以及一些習慣大部分人還是使用大 O 比較多。為了避免初學者增加額外的負擔以及看到嚴謹數學就頭痛的壓力，本篇還是以大 O 來介紹，漸進符號的較嚴謹數學定義可見：
http://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html#com簡單來說，O（大歐）代表的是「演算法執行步驟數目上限」，Ω（大歐美加 Omega）代表的是下限，而 Θ(大細塔)則代表演算法執行步驟數目同時滿足的上限與下限（不多不少剛剛好）。
【AppWorks School Batch #12 限時招生中】
AppWorks School 將開設 Android、iOS、Front-End 與 Backend Class 四個不同技能的訓練班次，全程免費，透過線上學習 4 週，駐點集訓 16 週的專案導向訓練，幫助你成為軟體工程師。
歡迎想成為軟體工程師的朋友，把握機會申請，報名到 7/22 23:59 截止喔！～https://bit.ly/2BUQmvn
嗨，我是程維，目前在美國 Google 擔任軟體工程師。如果你對入門機器學習、深度學習、人工智慧和大語言模型有興趣，我目前在準備一系列入門的文章。歡迎在這個網頁表單輸入你的電子信箱，我會在寫好的第一時間將文章寄送給你。
