Loading...

我們常會聽到「演算法」和「運算思維」這兩個名詞,但卻不太了解他們實際的意涵。演算法和運算思維,除了是學習程式的重要基礎,也能幫助你邏輯思考、解決問題。這篇文章就用實際的範例,帶你了解演算法和運算思維是什麼?以及學習他們的重要性。

什麼是運算思維(Computational Thinking)?

運算思維是一種思考過程。微軟研究院全球副總裁周以真(Jeannette Wing)對運算思維的定義如下:

運算思維是一個思考的程序。它的目的是闡明問題,並呈現其解決方案,因而讓「運算器」(包括機器與人) 能夠有效率地執行。」

為什麼要談運算思維呢?因為程式設計基本上就是和電腦溝通。更確切地說,學習寫程式就是學習如何下指令給電腦執行。因此,在學習程式語言之前,我們必須先了解、熟悉撰寫程式背後的「思考模式」。

「軟體工程師的工作就是轉換,把經營或管理的模糊概念轉換成程式碼。」軟體工程師 Weiliang Chew

開始學寫程式之前,我們不妨回顧運算思維的基本步驟,才能練習如何透過程式碼給電腦指令,在未來不斷更上層樓。

為什麼要學運算思維?

培養運算思維能訓練邏輯思考、提升問題解決能力。你會學習如何拆解問題,一步一步找到最有效的解決方法。學習運算思維也有助於了解電腦的運作模式,也就是電腦如何「思考」和執行指令。有了這些知識,你就更能有效運用科技解決問題。

無論你想解決什麼問題,運算思維能幫助你分析問題、找到核心議題,並採取適合的解決方法或工具(例如程式語言)。需要和工程師或技術團隊合作時,發揮運算思維能促進彼此之間的溝通、增加你的工作效率,也有助培養跨領域的技能。

從程式設計入門,建立電腦運算思維

用病毒擴散練習運算思維

想像自己在看一部電影,電影裡有個可怕的病毒,任何人只要感染到病毒都會變成殭屍!製造病毒的科學家告訴女主角說:「這種病毒的細胞每一秒就會分裂一次。」

電影情節有如世界末日來臨,你突然想到:如果病毒一開始是單一細胞,10 秒之後會有多少個病毒呢?

運算思維的四大步驟

運算思維的四大步驟定義如下:

我們可以把四步驟流程應用到思考過程中,進一步計算殭屍病毒的擴散:

1. 拆解 (decomposition)

將複雜的問題或系統分解成更⼩、更易於管理的問題。

意識到病毒細胞的數量,取決分裂了多少次,而分裂了多少次,又取決於時間過了幾秒鐘

可知病毒細胞的數量是由細胞分裂的次數決定,細胞分裂的次數則是由經歷的時間決定。

2. 辨識規律 (pattern recognition)

將每個⼩問題分別檢視,思考之前是否有解過類似的問題。

可以看到細胞數量每秒增長為兩倍,所以數量成長的規律非常清楚。

3.抽象化 (abstraction)

抓出重要的細節,將它轉化爲解決⽅案中的步驟。

能用數學公式 (1 x 2 x 2 x 2 x ... x 2) 寫出病毒細胞的數量與時間的關係。

演算法 (algorithm)設計

歸納出簡單的步驟或原則來解決每個⼩問題。在這個階段,你會定義要給電腦的輸入,以及電腦傳回的輸出。你也會定義電腦將執行的演算法。

設定【病毒細胞的數量 = 1 x 2^t,t 就是過了幾秒】這公式

如果以這四個步驟套回去剛剛的案例:其實在日常生活中,我們常常會用到運算思維。重要的是讓自己習慣用這個思考過程 (thinking process) 去拆解問題,然後把解決方案 (也是演算法) 透過程式碼去跟電腦溝通,讓電腦執行。

運算思維並不能回答我們遇到的所有問題,但提供了一個模式,讓我們能遵循清楚的流程,有系統地描述問題並加以解決。不只如此,運算思維也幫助我們找到能輕鬆轉換成程式碼的解決方法。所以,我們應該從日常生活的問題開始,培養運算思維的能力。現在就來看看一個在日常生活中應用運算思維的例子。

什麼是演算法(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。

如何評估演算法?

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

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

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

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

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

總結

軟體開發其中一個核心技能,就是把我們想解決的問題 (或想完成的事情),整理成有條理的指令,再用電腦的邏輯與語言去跟它溝通,讓它用最有效的方法去執行。當你認識並開始深入學習演算法和運算思維,你也更能夠順利地和電腦溝通、更有效地解決問題。

三分鐘小測驗,找到學習程式開發的入口

成為企業渴求的程式人才!

在家學會 JavaScript 網路開發

全新「全端 Web App 開發」課程,給你看得見的學習成效!
超過 90% 轉職成功,400 位來自亞洲各國的 ALPHA Camp 校友,畢業後達成轉職、創業、出國工作的夢想!

3 分鐘選課指南

給期待創新改變的你

前端x後端x全端 完整工程師技能樹

90% 學生轉職成功,職涯競爭力更上層樓
最專業的「全端 Web App 開發」課程,上班族邊工作也能同時培養第二專長!

3 分鐘選課指南

學期一|程式設計入門

零基礎也學得會的程式入門課!

開始學帶得走的技能,為自己未來的成長鋪路

學期二|掌握網頁開發

系統化學習 JavaScript

實作打好前後端基礎,成為扎實的網頁開發者

學期三|軟體工程師養成

養成業界接軌的實戰能力

前端/全端工程師專修路徑,完成技能與求職準備,成為業界即戰力