本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

我們生活中隨時隨地都在做出選擇，而在做選擇時，我們都會根據利弊進行判斷，今天要講的演算法適用於這種狀況。

Time and Space Tradeoff的概念

在設計演算法的時候，有些時候為了讓執行速度加快，我們可以使用更多內存去儲存資料，藉此減少迴圈數；反之，如果內存不足，可能所設計的演算法就會有更多的迴圈，而導致執行時間變長，這也算是一種利弊取捨，同時也是Time and Space Tradeoff的概念，我們在時間和空間中進行取捨，而這兩天我們會介紹的兩種方式都是利用空間換取時間（畢竟現在要加大記憶體也不是什麼難事了）。

輸入增進計畫(Input Enhancement)-Counting Sort

Input Enhancement的主要訴求，就是針對輸入值進行預處理，就像如果用樹幹製作的傢俱，在製作前需要先將樹幹的樹皮移除，而演算法處理資料也會有這種概念，在經過這種預處理後產生的資料，可能會需要使用更多的儲存空間來保存，然而卻可以大幅加速產生對應的結果，因此在這種狀況下，時間的利遠大於空間的弊，就像我們下面要講的Sort by Counting。

Distribution Sorting

如果要針對一個包含數個重複數值的陣列進行排序，原本的作法可能是：

1. 寫一個迴圈，找出最小的值。
2. 再寫一個迴圈，計算這個值重複幾次。
3. 再把這個值依照他重複的次數放到一個新的陣列當中。
4. 將原本的陣列中的所有這個值刪除。
5. 重複1~5步，直到初始陣列為空。

上面這個步驟沒有太大的毛病，但是可以更好，所以我們可以改良成下面的方式，也就是所謂的Distribution Sort：

1. 透過一個迴圈將初始陣列中所有數值及其重複次數記錄到另一個物件當中（Map/Dictionary）。
2. 改變這個Map/Dictionary的Value（後一個的值加上前一個的值）。
3. 再利用這個改變後的Map/Dictionary配合初始陣列，一步一步地將排序的結果生成。

第一種做法就只會有兩個參數：當前的值和重複的次數，以及兩個陣列（一新一舊），而第二種做法就會多一個Map/Dictionary的物件和兩個陣列，而這個Map/Dictionary中記錄了所有的值和個別重複的次數，因此所使用的空間比較多，但是節省了執行時間，因此Distribution Sort是一種Time and Space Tradeoff。

我們透過下面GIF來更加了解這個過程，首先先針對Array當中所有的值計算重複次數，記錄到一個Key-Value的物件中，然後再利用初始陣列Backward的順序，配合這個Key-Value的物件將值放到新陣列中對應的位置，並將Key-Value的Value減一（下一次的位置），反覆進行，即可得到排序後的結果。

小結

1. 空間換取時間，抑或時間換取空間，就是Time and Space Tradeoff的概念。
2. Distribution Sort會利用額外的空間來記錄過渡狀態，並利用過渡狀態進行排列。

預告

明天我們將會介紹另一種Time and Space Tradeoff的演算法 - hashing。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin