“《演算法圖鑑》：重新排列50個數，需要花費比宇宙歷史更長的時間？ - The News Lens 關鍵評論網…”

《演算法圖鑑》：重新排列50個數，需要花費比宇宙歷史更長的時間？ - The News Lens 關鍵評論網

Source

Photo credit: 臉譜出版

我們想讓你知道的是

能解決同一問題的演算法有多個時，要用哪個比較好？判斷演算法優劣的方法有很多。但一般而言，最重視的是執行時間，亦即輸入內容到輸出答案之間的時間。

文：石田保輝、宮崎修一

能解決同一問題的演算法有多個時，要用哪個比較好？判斷演算法優劣的方法有很多。

例如，簡單的演算法讓人輕鬆理解，也比較容易寫成程式。此外，執行中需要較少記憶體區的演算法，優點是在記憶體容量較小的電腦上也能順利運作。

但一般而言，最重視的是執行時間，亦即輸入內容到輸出答案之間的時間。

重新排列50個數需要花費比宇宙歷史更長的時間？

為了體驗使用低效率演算法的結果，請見如下關於排序的演算法說明：

1. 製作一個由n個數排列而成的數列（必須是之前沒出現過的排列方式）。
2. 如果步驟1產生的數列是從左開始由小到大排列，就輸出這個數列。若非由小到大的排列就回到步驟1，重新排序數列。

把這個演算法稱為「全域搜尋演算法」吧。全域搜尋會確認所有的排列組合，所以不管輸入什麼樣的數列，一定會輸出正確答案。

不過，要等多久才會有答案呢？運氣好的話，非常快就可以找出答案並輸出。但實際上無法期待結果一定如此，考慮到不順利的情況，若最後一個確認的數列才是正確答案，就必須確認所有的排列方式。

n個數的排列方式有n!種（n! ＝ n(n-1)(n-2)⋯⋯3・2・1）。當n＝50，情況如下：
50! ＝ 50・49・48⋯⋯3・2・1 ＞ 50・49・48⋯⋯13・12・11 ＞ 10⁴⁰

第一個不等號是捨去10以下的數。第二個不等號是成立於不等號左邊排列了40個大於10的數。

假設使用高性能電腦，1秒可以確認1兆（＝ 10¹²）個數列，那麼需要10⁴⁰÷10¹²＝10²⁸秒。1年等於31,536,000秒，小於10⁸秒。因此，10²⁸秒＞ 10²⁰ 年。

起源於大霹靂的宇宙年齡推測約137億年，比10¹¹年還短。換言之，使用全域搜尋演算法，就算只是排序50個數，等上宇宙年齡的10⁹倍也等不到答案。

Photo credit: 臉譜出版

如果是運用前述的選擇排序會如何呢？

首先，在第1回合中為了找出最小的數，從左邊開始一一確認數列的每個數，所以只要確認n個數即可。接著，第2回合是從n-1個數當中找出最小值，所以也只要確認n-1個數。像這樣持續進行到第n回合，確認這些數的整個過程所進行的回合數如下所示：
n＋(n-1)＋(n-2)＋…3＋2＋1 ＝ n(n＋1) / 2 ≦ n²

n＝50時，n²＝2500。若1秒可以確認1兆（＝10¹²）個數，則2500÷10¹²＝0.0000000025秒就可求出答案。與全域搜尋相較，選擇排序的速度絕對更快。

書籍介紹

本文摘錄自《演算法圖鑑【全新增訂版】：33種演算法 + 7種資料結構，人工智慧、數據分析、邏輯思考的原理和應用全圖解》，臉譜出版

作者：石田保輝、宮崎修一

• momo網路書店
• Readmoo讀墨電子書
• Pubu電子書城結帳時輸入TNL83，可享全站83折優惠（部分商品除外，如實體、成人及指定優惠商品，不得與其他優惠併用）
• 透過以上連結購書，《關鍵評論網》將由此獲得分潤收益。

現今我們的世界已離不開演算法，從線上搜尋、社群交友、法院判案、醫學診斷、金融運作、大腦決策到人工智慧的未來，越了解演算法，越可能掌控權力，成為時代的贏家。有些演算法對我們有益、有些有用，有些則可能使我們陷入大麻煩，但我們對這些演算法所知極少。

不管用哪種程式語言編寫程式，演算法都是不可或缺的，不過如果認為只有學電腦的人才要了解演算法，那就太可惜了。演算法其實是一連串解決問題的邏輯步驟，只要熟悉這些步驟和運用方式，每個人都能設計自己的演算法並應用於各種不同領域。學習演算法正是建構嚴謹思維和幫助做出最佳判斷的訓練。

█ 演算法的第一本書，從基礎開始學習！

演算法是用以執行計算或完成作業的程序，可以想像成料理食譜，如果做出某種料理的步驟是食譜，那麼用電腦解出特定問題的步驟就是演算法了。然而，食譜與演算法的決定性差異，在於演算法非常嚴謹。相較於食譜有很多概略的描述，演算法的所有步驟都用數學方式表現，沒有模糊地帶。

本書蒐羅介紹33種基本的演算法和7種資料結構，貨真價實完全圖解。每一個步驟都以圖片和文字詳細說明，拆解具體演算過程，逐步建立邏輯概念，輕鬆進入演算法的世界。

書中解說的演算法範疇包括「排序」、「陣列搜尋」、「圖形搜尋」、「安全性演算法」、「分群」，以及「網頁排名」等各種廣泛使用的基礎演算法。不用艱澀的專有名詞，步步口語分解，完全沒有概念的人也能漸進學習。

Photo credit: 臉譜出版

【加入關鍵評論網會員】每天精彩好文直送你的信箱，每週獨享編輯精選、時事精選、藝文週報等特製電子報。還可留言與作者、記者、編輯討論文章內容。立刻點擊免費加入會員！

責任編輯：林奕甫
核稿編輯：翁世航

Sent with Email Tabs, a Firefox Test Pilot experiment