《演算法圖鑑》第一章：資料結構
經過 Honestbee 技術面試的洗禮後，積極的思索如何針對 Honestbee feedback 的建議去更進一步精進自己所不足的部分。經歸納後，將先從資料結構及演算法的基礎開始補強，在同事的推薦下買了《演算法圖鑑》這本書。這本書整理了 26 種基本的演算法和 7 種的資料結構，透過圖像和文字來闡述演算的步驟和過程，協助讀者建立演算法的基礎概念。
接著將 2019 第一週所看完的第一章「資料結構」做個簡要的筆記。
何謂資料結構？
資料儲存在電腦記憶體中時，決定資料的順序和位置的，就是資料結構 ( Data Structure )。
串列 / 列表 ( List )
- 列表 ( List ) 結構的資料會排成一直線，便於追加或刪除，缺點是存取資料較費時。
- 每一個資料和一個指標 ( Pointer ) 配對，指向下一筆資料在記憶體中的位址。
- 常見的列表種類：
鏈結串列 ( Linked List ) : 一個資料連一個資料的結構
使用列表要多少執行時間？
假設儲存在列表中的資料有 n 個，存取資料時必須由列表最前端開始 ( 線性搜尋 Linear Search )，若想存取的資料在很後面時，需要花費 O(n) 的執行時間。
而在已經確定要追加資料的存取位置時進行資料追加，只需改變 2 個指標的指向，所以是與 n 無關的常數時間 O(1)。
同理，刪除資料耗費的時間也是與 n 無關的常數時間 O(1)。
陣列 ( Array )
- 陣列 ( Array ) 結構由相同類型的元素 ( Element ) 的集合所組成，相較於 List 更便於進行資料的存取，但追加/刪除資料卻比 List 更費力。
- 因為儲存為連續的，所以能透過索引 ( Index ) 來計算出記憶體位址，進而直接存取每個資料，這種存取方式稱為「隨機存取 ( Random Access )」或「直接存取」。
使用陣列要多少執行時間？
假設儲存在陣列中的資料有 n 個，因為能隨機存取，所以可以用常數 O(1) 的時間來存取。
追加數據時，必須將指定位址後方所有的數據分別往後移。例如在陣列最前端追加/刪除資料時，就需要 O(n) 的時間。
堆疊 ( Stack )
- 堆疊 ( Stack ) 結構類似由上而下堆放的概念，若要針對資料進行操作只能從資料最新的那一端開始，只允許在一端進行操作。
- 追加資料稱為「推入( Push )」。
- 輸出資料稱為「彈出 ( Pop)」。
- 堆疊 ( Stack ) 原理為後進先出 ( Last In First Out )，縮寫 LIFO。
佇列 ( Queue )
- 佇列 ( Queue) 的結構類似堆疊，但差異在於佇列可以在兩端進行資料的操作。
- 佇列只允許在後端（稱為 rear）追加資料至佇列中，這種操作稱為「進入佇列 ( Enqueue)」。
- 佇列只允許在前端（稱為 front）從佇列中輸出資料，這種操作稱為「輸出佇列 ( Dequeue)」。
- 佇列原理為先進先出 ( First In First Out )，縮寫 FIFO。
雜湊表 ( Hash Table )
- 雜湊表 ( Hash Table ) 的資料結構，是由「雜湊函數 ( Hash Function)」有效率地進行數據搜尋。
- 儲存的資料為成對的鍵 ( Key ) 和值 ( Value )。
- 使用雜湊函數計算出資料的鍵所對應的雜湊值，並透過餘數運算取得餘數值，並將該數值作為索引位址，最後將資料存入該位置中。
- 當兩筆或兩筆以上不同的資料，經過雜湊函數和餘數運算後得到相同的值，也就是資料的儲存位置重複時，稱為「碰撞 ( Collision ) 」。
- 發生碰撞時，可以藉由列表將資料接續在先前已存入的資料之後，這種方法稱為「額外鏈結法 ( Separate Chaining )」。
- 發生碰撞時，最廣為應用的為「開放定址法 ( Open Addresssing )」。發生碰撞會求出第二候補位址並儲存，若位址已滿則會繼續找下一個候補位址，直至找到空的位址。
- 雜湊表主要可以分作兩大類：「額外鏈結法 ( Separate Chaining )」 以及「開放定址法 ( Open Addresssing )」。
- 其中「開放定址法 ( Open Addresssing )」根據資料存放的邏輯又分成兩種方法：「線性探測法 ( Linear Probing) 」及 「二次探查 ( Quadratic Probing) 」。[ 參考資料: http://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html ]
- 雜湊表能夠彈性儲存數據，又可以快速讀取數據，常用於程式語言的關聯陣列 ( Associative Array )。
雜湊表需要多少執行時間？
平均情況：搜尋、插入、刪除，皆為 O(1)
最壞情況：搜尋、插入、刪除，皆為 O(n)
參考資料:
堆積 ( Heap )
- 堆積 ( Heap ) 是圖形的樹狀資料結構，用於實踐「優先佇列 ( Priority Queue) 」。
- 優先佇列 ( Priority Queue) 是資料結構的一種，每個元素都有各自的優先級，優先級最高的元素最先得到服務。[ 參考資料：http://alrightchiu.github.io/SecondRound/priority-queueintrojian-jie.html]
- 用來表示堆積的樹狀結構中，各個點稱為「節點 ( Node )」，資料被儲存於各個節點中。
- 堆積的每個節點最多可以擁有兩個子節點 ( Child Node )。
- 在堆積中儲存資料的規則1：子節點必須父節點 ( Father Node) 大。因此最小的資料會被存入樹狀結構的最上方，稱為「根 ( Root ) 」。
- 在堆積中儲存資料的規則2：追加資料時，會從最下層的節點開始加入資料。當最下層被填滿時，往下產生新的一階，並再從左方開始追加資料。
堆積需要多少執行時間？
因為最小值永遠在最上方，所以無論數據有多少個，取出最小值都只需要 O(1)。
取出資料後，重整堆積的結構時，必須將最尾端最後一個資料放到最上方的節點，與子節點進行比較，比較後再依據規則進行排序。因此執行時間與樹狀結構的高度成等比。若數據個數為 n 個，根據樹狀結構的條件得知，高為 log2(n) 即為 2 的 n 次方，重整的時間為 O(log n)。
同理，在最尾端追加資料後，需反覆與父節點進行比較及重新排序直到滿足堆積規則，所以也是需要與樹狀結構的高成等比的時間 O(log n)。
二元搜尋樹 ( Binary Search Tree )
- 二元搜尋樹 ( Binary Search Tree ) 是圖形的樹狀資料結構。
- 特性一：若任意節點的左子樹不空，則所有節點上的資料都會大於連結在其左邊節點上的資料。左子樹上所有節點的值均小於它的根節點的值，所以最左側的節點即為最小的資料。
- 特性二：若任意節點的右子樹不空，則所有節點上的數據都會小於連結在其右邊節點上的資料。右子樹上所有節點的值均大於它的根節點的值，所以最右側的節點即為最大的資料。
二元搜尋樹需要多少執行時間？
比較的次數與樹狀結構的高度相同，也就是說當有 n 個節點，樹狀結構的結構達到平衡時，最多只要進行 log2(n) 次的比較和移動，因此時間為 O(log n)。
但是，當樹狀結構靠攏成縱向一直線的形狀時，結構將會變得很高，執行時間則會變差為 O(n)。
參考資料：
