程式、演算法差在哪?比起學程式,你更應該了解演算法

【為什麼我們要挑選這篇文章】電腦科技突飛猛進,未來,程式語言將會跟英文一樣,是每個工作者的必備技能。

IT 知識,就是你的競爭力》的作者是 GLOBIS 商學院,它是日本最大的商學院。這本書用淺顯易懂的語言,讓沒有程式背景的人也能輕鬆了解,領略程式的概念。下文,我們將了解程式與演算法的差別,以及著名的排序演算法:氣泡排序法。(責任編輯:郭家宏)

程式到底是什麼東西呢?

除了 C 語言或 Java ,程式語言還有相當多種,光是主要類型就高達兩百種以上。每種程式語言都各有其特徵,例如人類也容易理解、適合人工智慧、處理速度快等,會根據用途的不同而選擇使用特定的語言。

電腦記住程式語言,就好像人類習得英語、日語等的過程一樣。必須一一仔細記住文法、詞彙、說法。

程式設計師會記住這些語言,在各種工作現場活用這些知識,時時磨練自己的功夫。

演算法:電腦的思考程序

不過一般的職場工作者有必要記住這些程式語言嗎?以結論來講,雖然學會最好,但 比起各種程式語言,最好優先了解演算法。

所謂的演算法,就是「利用電腦解決所賦予任務的處理順序」。

一般而言,演算法不會依靠程式語言(C 語言、Java 等)。無論你學哪一種程式語言,演算法的思維都通用。也就是說:

.演算法相當於「思考程序」
.程式相當於為了表現演算法的「語言」

光只是學習說話方法,並不會深化思考,更不會產生出新點子。身為一般的商務人士,重點在於了解演算法。

那麼,演算法到底是什麼?舉個排列名片的例子說明。

準備好 50 張姓名完全不同的名片,用自己喜歡的方法,按照日文五十音的順序排序。實際動手試排,速度快的人要花 7 分鐘,慢的人大概得花 15 分鐘左右才能排完。

該如何用更快速的方法排列名片這個「課題本身的解法」,就相當於演算法。

例如,首先將名片依日文 A 行到 WA 行分為十座山,每座山按照母音分為五組,就能依 50 音順利輕鬆分類 50 張名片。

不過,電腦並不像各位讀者一樣厲害。 如果是人類,能夠綜觀映入眼簾的大範圍事物,但是電腦能做到的,只有慢慢取出主記憶體內的資料。 由這個案例來看,電腦只能一一瀏覽每張名片,無法相互比較,也無法互相替換。

那麼,你要如何下命令,讓這樣的電腦排列名片呢?解題的方法就是演算法。

氣泡排序法:最具代表性的排序演算法

許多演算法都可以排列名片,最具代表性的演算法就是「氣泡排序法」(Bubble sort)。我在下頁圖中,將數字 1 至 5 隨機排列,接著將圖中數字重新由小排到大。

首先比較從右邊數來的兩個數字,如果左邊的數字大於右邊的數字就替換兩者,右邊的數字比較大就不必移動。

例如,比較圖中右邊的兩個數字,2(左)和 1(右)相比後,發覺 2(左)比較大,因此兩者就互相替換;接著,相同地,再將比較後的數字逐一與左方數字相比。此時 5(左)和 1(右)相比後,由於 5(左)比較大,因此就進行替換。

比較到最左邊的數字,完成替換後,最左邊的數字就變成最小的數字。

圖中,數字 1 已經在最左邊的位置。然後再度從右邊做同樣的事。接著,這次數字 2 會來到左邊數來的第二格。基本上要不斷重複這個作業。這就好像將浮出的泡沫排列替換的方法,因此叫做「氣泡排序法」。

接著再介紹另一種排序方法。就像下圖所示,以最右邊的數字 4 為基準值將比 4 還小的數字放在 4 的左邊,將比 4 還大的數字放在 4 的右邊。

此時不用在意排的順序。接著,數字 4 會自動變成從左邊數來的第 4 個數字。

接著,分為比 4 小的(2、1、3)及比 4 大的(7、8、5、6)兩組,進行同樣的作業。例如數字較小的那組,就用最右邊的數字 3 當作基準值,比 3 小的數字放在左邊,比 3 大的數字放在右邊。

同樣的,比 4 大的那組中,將最右邊的數字 6 當作基準值,比 6 小的數字放在左邊,比 6 大的數字放在右邊。在各組的數字只剩一個之前,進行同樣的作業,結果就能將 1 至 8 按順序排序。

這是叫做「快速排序」(Quicksort)的演算法,如名稱所述,能夠非常快速進行排序。不過有些人會覺得難以理解,也會有人覺得更加費工。

愈好的演算法,「計算量」就愈少

在演算法領域,為了判斷好壞,會使用「計算量」的概念。我們可將「取出一個資料,進行比較、交換」的作業當作一種計算,而根據不同的演算法,也能測出計算量的差異。

那麼,氣泡排序法的計算量又有多大呢?上文介紹了 50 張名片,以及 8 個數字,接下來將要進行排列的對象數設為 n 個。首先從右邊比較、排序 n 次(下頁圖的灰色箭頭),接著進行 n 次這種作業(同一張圖的黃色箭頭)。

接著,進行 n 次比較、交換 n 次的作業,會發生最多 n^2 次的計算(正確來講是 n(n - 1)/2,在此不講解細節。請記得,大概就是接近 n^2 的數字)。

快速排序法中,n 次的比較(橫向箭頭)雖然一樣,但是縱的深度會成為 log2(n)。log2(n) 是數學的對數的思考方式,就是 2 要乘以幾次才會變成 n。例如 log2(32) 是 5,log2(1,000) 大約是 10。

此時,就將 n 個單位各自分為二個,即為 log2(n)。如果 n 是 8,就是 log2(8) = 3,如圖示,縱向有三層的結構。只要進行三次這種作業,就能結束排序。計算量是用 log2(n) 來計算 n  次,所以就是 n×log2(n) 。

接著,我們來看 n^2 及 n×log2(n) 的計算量相差多少。將橫軸設為 n,並將計算量的大小圖表化,即為下圖。只要 n 愈大,計算量就會出現壓倒性的影響,一目瞭然。

(本文書摘內容出自《IT 知識,就是你的競爭力》,由 商業周刊 授權轉載,並同意 TechOrange 編寫導讀與修訂標題。首圖來源:Pixabay CC Licensed

更多程式相關知識

求職市場最搶手的 5 個程式語言技能,Python、Java 居然都沒上榜!
Python 早就落伍了!AI 權威 LeCun 直言:深度學習需要更靈活的程式語言
GitHub 神人整理出一份 Python 開源清單:15 個領域、181 個開源項目任你用


我們正在找夥伴!

2019 年我們的團隊正在大舉擴張,需要你的加入跟我們一起找出台灣創新原動力! 我們正在徵 《採訪社群編輯》、《助理編輯》,詳細職缺與應徵辦法 請點我

點關鍵字看更多相關文章: