哈囉！久違又來更新教學文系列了，這次的主題是在學完基礎程式設計後，一定也需要會的東西：資料結構與演算法。若你對程式設計還不太熟悉，或是想回去複習一下 Python 或 C++，可以參考我下面的系列文：

這個系列文應該會很長，因為 DSA（i.e. Data Structure and Algorithm）這個主題是在是涵蓋太多東西了，甚至我寫的內容也沒有到很完整。這次的來源一樣是拿來做家教講義，文字部分不會太詳盡，有需要更詳盡的內容歡迎聯絡我，如果我有空就可以幫你上課 XD。

最後就是轉載請記得標註來源，這裡面的內容都是作者本人收集的心血！

HackMD 完整版請點我

入門介紹

來複習一下學習地圖，以臺大資工系必修為例：

以臺大資管系必修為例：

而在演算法與資料結構的世界裡面，大概又可以分為以下幾種類別。在我們之後的課程中，會逐漸的介紹每個名詞以及其對應概念：
image

相關連結：

競賽相關

適合國 / 高中生參加的相關競賽有以下：

建議可以向學校老師或相關社團與補習班詢問更多細節。

APCS Practice

  • 應試相關資訊
    • 建議每項都要讀過，特別是環境 / 作答系統 / 考場規則

實作題

觀念題

相關資源

排序演算法（Sorting Algorithms）

image

排序演算法是一種將一組資料按照特定規則重新排列的方法。

常見的排序方法有：

  • 選擇排序法(Selection Sort)
    每次挑最大或最小的，依序移動到對應的位置。
  • 插入排序法(Insertion Sort)
    照順序每次拿一個，並插入正確的位置。
  • 氣泡排序法(Bubble Sort)
    就像有個氣泡，兩兩比對後留下大的，每次都把最大的帶到最後面。
  • 合併排序法(Merge Sort)
    將陣列不斷細分，再將細分後的結果兩兩合併。
  • 快速排序法(Quick Sort)
    選定一個 Pivot，將比他小的丟左邊比他大的丟右邊，再針對左右兩部分進行一次相同的事情。

練習：試著實作以上五種常見的 Sorting 方法吧！

推薦參考：介紹排序演算法的網站
推薦參考：寫程式的基本功：排序演算法
補充：Python 中的 sorting、C++ 中的 sorting
補充：最貼近現實的排序演算法 - Timsort

補充：還有一些很奇怪的排序方法，看了會覺得很傻眼又好笑。如果有興趣可以參考 10 Forbidden Sorting Algorithms ，舉幾個例子像是：

  • Bogo 排序法（Bogo Sort）
    一直隨機重新排序，直到剛好符合大小順序。（猴子打字機定理）
  • 史達林排序法（Stalin’s Sort）
    遇到大小順序不對的就直接刪掉。（所以最後的 list 有可能比原本的短）

搜尋演算法（Search Algorithms）

image

搜尋演算法是一種用來在資料集中尋找特定項目的方法或步驟。

適用於未排序或已排序的資料

線性搜尋（Linear Search）

直接一項一項搜尋，直到找到要的東西為止。
最基本的搜尋方式，時間複雜度為 $O(N)$。

僅適用於排序的資料

以下的搜尋演算法，會利用資料已經排序過的性質，來加速搜尋的過程。

二分搜尋（Binary Search）

很重要的搜尋演算法！將資料中間的與目標相比，若目標較大則往右再做一次搜尋，目標較小則往左，直到找到為止，可以參考 二分搜尋法教學 與 二分搜尋法的一些細節。

Leetcode:

指數搜尋（Exponential Search）

與二分搜尋類似，只是使用 2^N 作為搜尋的 index。

插補搜尋（Interpolation Search）

用線性插值的概念，來加速尋找的過程。

推薦參考：寫程式的基本功：搜尋演算法

時間複雜度（Time Complexity）

時間複雜度是衡量演算法執行效率的一個重要指標，表示隨著輸入規模增加，算法執行所需時間的增長速度。

常用的符號有：

  • O-Notation：Big-O（Worst Case，最差）
  • Θ-Notation：Big-Theta（Average Case，平均）
  • Ω−Notation：Big-Omega（Best Case，最佳）

一般來說，我們最關心的是最差狀況下的時間複雜度（Big-O），關於詳細的數學推導可以參見補充。一些常見的時間複雜度與其例子為：

  • $O(1)$：陣列讀取
  • $O(n)$：簡易搜尋
  • $O(log n)$：二分搜尋
  • $O(nlogn)$：合併排序
  • $O(n^2)$：選擇排序
  • $O(2^n)$：費波那契數列（遞迴版本）

我們來看看這些例子是如何被計算出來的：

補充：複雜度與漸進符號之數學
補充：時間複雜度與空間複雜度

補充：Complexity Cheat Sheet

若不知道圖中的資料結構是什麼的話，可以先往下看。