Ox-Blog

引言

在2024年元旦離世的電腦科學家尼克勞斯·埃米爾·維爾特( Niklaus Emil Wirth )，亦即Pascal 語言的主設計師，他在1976年曾着有一書，可以說是奠基了數據導向編程的大方向。
很可惜的我暫時還未讀過這本書，在此引用此書的原因單純只因為它的書名 : 「Algorithms + Data Structures = Programs」。

數據結構可以說是一個對不少初階到中階開發者都既熟識又陌生的名字，幾乎每本編程教學的書都會提到它，但幾乎每一個讀這些書的新人們都會把它跳過，畢竟對基礎開發而言它的幫助的確不大，但如果開發的目的產物是需要高效能、高運算速度的話，那數據結構可以說是不可或缺的關注點。
例如遊戲編程需要在最多1/60秒內完成上萬或上十萬個計算，大型的數據庫數據讀取要整合無數條數據，那利用數據結構和演算法走走捷徑便是必須的。

數據結構介紹

數據結構是什麼 ? 數據結構指的是數據的儲存和組織的方式。聽起來有些抽象，但可以理解成一個宏觀世界雜物的擺方式，例如 : 房間有1 到 6 集的沙丘小說 ，你可以選擇把小說隨地堆積在地上，也可以以集數由大至小由左至右擺放，也可以分成兩排，一排奇數集、一排偶數集。

不同的擺放方式，都有他存在的目的。

如果書本隨地堆積在地上的話，便可以快速的隨機加入書本，畢竟隨手一放就算加完成了嘛 ;
但要找尋特定的一集小說，便要每本每本的檢查，效率便會大幅下降。

如果由大至小由左至右擺放的話，找尋最早或最晚的集數便非常容易。

如何表達效能快慢

數據結構的效能並不能單純用時間來表示，而需要用大O符號( Big O notation )。
同樣以小說來作例子，要在一堆書本中找尋特定集數的沙丘的話，就必須要一本一本的翻查，但不同人的手速都不相同，有人翻查一本的時間較快，有人可能比較手忙腳亂，使得最後完成任務所消耗的時間也不儘相同，以電腦的角度來說便是中央處理器(CPU)的速度差。為了要更準確的進行不同方法的效能比較，就必須要有統一的標準。
那便是完成運算的步驟總數亦即時間複雜度( Time Complexity )，而表達的方式就是大O符號。

大O符號介紹

大O符號是一種數學符號，由一個O以及開關括號(  )組成。

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

以上三個是最常出現的三種大O符號對時間複雜度的表達。括號中的是該運算完成所需要的步驟數，1為最低最優解，越大為表現得越差。

當然，除這三種以外還有無數種表達，
但了解這三種表達大概就能明白大O符號的邏輯。

演算法基礎和大O符號應用

在這我會根據3種上述所提及的時間複雜度來介紹幾個演算符合該時間複雜度的演算法，來介紹什麼是演算法並順便介紹不同的時間複雜度。

首先，括號中的數字所代表的是此運算方法所需要的步驟數，

O(1)指只需要一個步驟便能完成此運算 。
1. 以小說為例，如果一到六集的沙丘由小至大、左至右排列整齊，那想取得最早的一本小說便
拿起最左的一本小說便可，數據結構以C#來說便是SortedList。
2. 以小說為例，如果每一本書都以書脊向着執行者，那對執行者而要只需看一眼便知道哪一本
小說是在尋找的集數，數據結構以C#來說便類似Dictionary或Python的dict或C++的map。
(當然這裡只是比喻，Dictionary本質是哈希表，和看書脊的邏輯不太相同，但這不是本文的
主題，便不多加着墨。)

由於上面兩個個例子都在數據結構的層級上就把運算步驟壓低至一步，
因此不需要設計一套演算法來完成運成。

O(n)指的則是有n個數據，就需要n個步驟才能完成運算。

1. 以小說為例，如果執行者不知道Franklin Herbert老頭子在出完第六集沙丘就駕鶴西歸，
並且書也沒做整理，但執行者想知道書堆中最大的集數是多少便必須要一本一本翻查，
並且在小本本( 記憶體 Ram )紀錄下最大的集數。

這裡的例子並沒有使用任何的數據結構，並且沒有使用任何演算法來完成運算，
使得運算的效率低下，是謂最糟的運算方式。

O(log n)指的則是有n個數據，就最少需要n的一半的個步驟才能完成運算。

1. 同樣以小說為例，如果5000本書堆中的其中一本書失竊了，只剩下4999本小說。
但書堆的主人擔心他最愛的第四集《沙丘神皇》還在不在，
因此他請執行者去檢查。所倖的是所有小說都以書本的ID排列好。
但如果只是一本一本翻，效率不會提高，因此需要演算法，
執行者可以用「終極密碼」的方式把4999本小說二分再二分，
確定找到或找不到目標書籍。而此演算法名為二分搜索法(Binary Search Algorithm)，
而使用的數據結構則是SortedList(C#)，其時間複雜度正是O(log n)

從以幾個例子來看就能明白，對開發者的角度來說O(1)是最理想的情況，而為了達到/接近O(1)，就需要適合其情境的數據結構，並在適合的數據結構上用適合的演算法。

另外提一嘴，Erase或者Remove是一個很奇妙且麻煩的東西，因為當我們要移除一個元素時，電腦並不會知道使用者想移除的元素是哪一個，在記憶體的哪一個位置，因此對大多數數據結構而言要進行移除時都需要Scan一次所有數據才會找到要移除的對象。一般的陣列、C++裡vector、list等等的無排序的數據結構都需要O(n)才能完成，像set (search tree)等的有排序的數據結構也需要O(log n)才能完成，只有hash table才能夠O(1)完成移除。

但這不代表hash table是個無敵的數據結構，因為雜湊化本身也要進行運算，有時光是雜湊化就比搜尋還要慢了，所以在小規模、經常被讀取的數據，用非雜湊的數據結構效能會更高，因此要不同情境下，用不同的數據結構。

實際情況

圖1