Loading...

什麼是演算法(Algorithm)?

在哈拉瑞的書《人類大命運:從智人到神人》中,他提到現在演算法「大概是世界上最重要的概念」。的確,從 Google 搜尋的排列順序到銀行的金融交易,生活中許多事都是由演算法主導。那麼,到底什麼是演算法呢?

「演算法是一系列有條理的步驟,能用於計算、解決問題、做出決定。」 - 《人類大命運:從智人到神人》

演算法的重點在於,如果環境和輸入不變,每次執行同一組指令時, 會得到相同的輸出。除了電腦程式之外,食譜和樂譜也是演算法的例子。

《星際大戰》演算法遊戲

想親身體驗演算法的話,不妨試試看這款《星際大戰》遊戲。

在遊戲中,你必須設定一組指令,才能引導 BB-8 機器人拿到廢金屬。這其實就是設計演算法的核心,建立一組指令來達到特定結果。下面我們將討論演算法的設計。

設計演算法

在設計演算法前,必須清楚定義輸入和輸出:

舉例來說,烤蛋糕時,你首先需要正確份量的原料(輸入),之後你會按照食譜(演算法)製作,最後烤出蛋糕(輸出)。

現在就用幾個例子來了解如何設計好的演算法。

例1:一起去度假吧!

假設你需要規畫和朋友一起出國旅行。你如何計算每個人需要花多少錢呢?

這是我們的輸入和輸出:

  • 輸入:旅行期間的支出項目、每個項目的費用、旅行天數、朋友人數
  • 輸出:每個人的旅行總花費

我們看一下背後的邏輯:我必須先算出一個人的花費,方法是加總旅行每個項目的費用,同時考量旅行天數。最後,我必須將一個人的總花費乘以參與旅行的總人數。

以下是演算法:

Step 1:旅行每個項目的費用(每人/每天)乘以天數

Step 2:將以上費用加總,再加上機票費用(一次性費用,而非每日支出)

Step 3:將每人費用乘以朋友人數

例2:騎士走棋盤

我們看另一個例子。在西洋棋裡,騎士的走法為「L」形,如下圖所示。

在「騎士走棋盤」遊戲中,你必須移動騎士走過棋盤上每一格。花 5 分鐘從這裡玩這個遊戲。試看看能不能每一格只走一次。

你想出的策略是什麼呢?一個可行策略是運用一種稱為「回溯法」(backtracking)的演算法,意思是隨機移動騎士,直到無法繼續移動到其他方格為止(或者所有方格都已經走過)。之後將騎士移回前一個位置,嘗試不同的路線。依此不斷重複,直到為騎士找到最佳的路線為止。

演算法看起來會像下表:

Step 1:移動騎士到新方格

Step 2:沒有其他可走方格,將騎士移回前一個位置

Step 3:重複步驟 1 直到騎士走過所有方格

如何知道自己的演算法是否正確?

檢測演算法的方式之一是將輸出未知的輸入放進演算法中。從輸出結果可以觀察演算法的效用,看看演算法是否產生理想輸出。如果沒有的話,我們能觀察輸出的規律,進而修正演算法,直到獲得理想輸出為止。

資料結構和演算法對一個工程師的意義?如何提升實力

演算法類型

演算法就和問題一樣有許多種類。以下是電腦科學領域常見的幾種演算法:

  • 簡單遞迴演算法 (Simple recursive algorithms:):這些演算法使用遞迴計算來找答案。這個方法用於解決古典問題,例如「計算到 n 次方」。
  • 回溯法 (Backtracking):為了找到解決方法,一個問題先劃分為多個計算用的路徑。如果路徑方向錯誤,便回到上一個位置,從另一個方向開始計算。常見的使用案例需要從大量數據中找到特定資訊。這個方法通常用來找出每一條路徑。如果一條路徑不包含目標資訊,則演算法會回到上一個連接點。
  • 動態法 (Dynamic): 這個演算法的獨特之處在於演算法會記憶之前解決過的問題,並藉由之前解決問題的經驗更快找到類似問題的解決方法。如果之前你計算過 n 的 1,000,000 次方,這個演算法不需從頭重新計算,而是能根據之前計算 n 的 1,000,001 次方的答案,更快找到解答。
  • 分而治之法 (Divide and conquer):排序是分而治之演算法常見的類型。這種演算法將一系列數字切分為多個部分,然後在每個部分進行比較排序。所有部分之後合併起來,整個組合會再次進行比較排序。這種方法的操作速度比只排序不分割的演算法還要快上好幾倍。
  • 暴力法 (Brute force):這是駭客最常使用的演算法。如果駭客想要駭入你的帳戶,大概會一次就嘗試所有可能的密碼組合。之所以稱為暴力演算法,是因為這個方法靠電腦速度暴力破解密碼。
  • 貪婪法 (Greedy):貪婪演算法和暴力演算法類似。這個解決方法會根據當前狀況,找出最佳解決方法,常用來尋找與決定行駛路線。演算法不會計算抵達目的地的所有可能路線,只選擇距離下一個檢查點最短的路線,而且不會考慮檢查點之後的其他路線。

演算法的應用

在這裡我們收集了幾個我們生活常碰到,而且有趣的演算法,請參考這幾個外部連結。

  • 排列 (Sorting) - 如何把千多本書排列順序
  • 秘書問題 (Secretary Problem) - 如果你要聘請一名秘書,總共有 n 個申請者。每次只能面試一人,面試後要馬上決定是否聘他,如果當時決定不聘他,就再沒有機會。問:要面試幾個人,才最有機會選中最合適的人選?解決這個問題的方法,叫「最佳停止演算法」(Optimal Stopping Algorithm).
  • PageRank - How Search Work by Google - Google 最早的是用 PageRank 這個演算法去判斷如何排列用戶搜尋的結果。
  • EdgeRank - Facebook 動態消息 (Newsfeed) 早期以一個叫 EdgeRank 的演算法來判斷用戶看到什麼訊息。這篇文章可以幫助你了解更多有關 EdgeRank。

演算法的應用場景:以計算平均股價為例

計算平均股價-未使用演算法

說明:假設有過去 100 天的股價,但只需要最近 20 天的平均股價,這段程式的確能計算出最後 20 天的平均價格,卻導致浪費了 80 個空間去儲存不需要的股價資料。如果要計算的數字越多,就會浪費更多的空間。

計算平均股價-使用演算法

說明:這段程式碼跟前一段相比,多加了宣告,把 list 變成固定長度,length 設為 20,最新的數字會把舊的數字蓋掉。所以不管股價資料幾筆,所需的執行空間都固定。如果拿評估演算法效能的指標 Big-O 來看,這個作法就是達到了空間複雜度 O(1) 的理想狀況。

從上述舉例可得知,演算法能提高程式碼的執行效率。特別是當使用者規模或資料量達一定程度時,應用演算法提升程式的效能就變得非常重要。

如何評估演算法?

演算法除了能否正確解決問題之外,還有「好、壞」之分嗎?答案是有的。不同的演算法,雖然都能正確達成目標,但還是有效能 (efficiency) 之分。主要的考量點有兩個:

  • 時間複雜度 (Time complexity) - 它代表一個演算法的執行時間。針對同一個問題,有些演算法會比別的用更短的時間(也是更快速)去解決問題。
  • 空間複雜度 (Space complexity) - 它指的是要執行該演算法 (或是程式碼) 所需的記憶體量。

可以理解,效能越好的演算法,它所需要的時間會越短、空間也越少。衡量時間、空間複雜度的方法我們叫 BigO notation. 你可能看過像這種符號:

  • O (1)
  • O (n)
  • O (n log n)

在這篇文章我們先不細談 BigO Notation。

演算法面試準備與LeetCode 刷題重點心法

演算法學習 Q&A

Q:學習演算法之前,需要有什麼樣的基礎嗎?

演算法算是獨立學問,不太需要基礎知識,但由於會使用 Big-O 來分析演算法效率,分析時會用到高中數學知識,如指數、對數等,所以還是要理解一些高中數學,假設真的忘了,碰到時再回頭補上即可。

Q:演算法會因程式語言不同而有差異嗎?

95% 邏輯是一樣的,但根據語言特性,實作細節寫法可能有點不同。如果要從零開始準備演算法面試,提供兩個面向供參考:

  • 選擇自己最熟悉的語言練習演算法:絕大多數公司在面試演算法時,不會要求使用的程式語言,因此可以用自己最拿手的程式語言來準備
  • 若無特別熟悉的程式語言,建議可以用 C 語言來學習演算法:由於 C 語言是很原始的程式語言,如果用 C 寫得出演算法,基本上其他語言也寫得出來

無論如何,程式語言只是工具,在準備演算法面試時,建議使用自己最拿手的武器去應戰。

Q:網路開發新手在做 side project 時,如何導入演算法思維?

其實蠻困難的,因為絕大多數前端應用軟體都用不到演算法,再者如果沒有演算法的概念,也無從應用起。只有當你具備演算法基礎知識時,做 project 才有機會用到演算法,因此在做 side project 時,可以反問自己:有沒有更棒的程式寫法。