前兩天我們討論了演算法的時間複雜度，今天開始學習 資料結構 (Data Structures)。

後面會介紹一些基本的資料結構，而今天會從最基本、最常見的結構開始：陣列 (Array) 與 矩陣 (Matrix)。

為甚麼會需要資料結構？

當我們寫程式時，程式不只是執行演算法，還需要存放與管理資料。

資料結構 (Data Structures) 就是用來存放與管理演算法所需要的資料。

資料結構通常會有一個 索引 (index) 來表示 index，跟一個 值 (value)，存放 index 所對應到的實際值

常見的操作則會有 查詢、修改，而不同的資料結構在 查詢、修改 所需要的時間複雜度也不同

所以選對資料結構也能讓演算法效率更好

再來就開始今天的 陣列 (Array) 與 矩陣 (Matrix)。

🔹陣列 (Array)

陣列是一個連續儲存資料的結構，以下是一些它的特點

• 特點：
  • 長度固定。
  • 透過 index 取值為 O(1)。
  • 插入與刪除元素可能成本較高，因為需要搬移其他元素（O(n)）。

假設我們有一個陣列 A，要取它第 3 個位置的值就可以寫 A[2] (index 從 0 開始)

但許多語言中陣列的長度是固定且無法改變，在很多演算法中會有點侷限，所以出現了動態陣列 (Dynamic Array)

• 像是 python 的 list 就算一種動態陣列

🔹矩陣 (Matrix)

矩陣是一個二維陣列，就是線性代數的矩陣在程式裡面怎麼表達，每次取值會需要兩個 index，像是 A[3][2] (取第 4 row，第 3 個值)

• 特點：

  • 用兩個索引（row, column）存取元素。
  • 適合表示座標、圖像、表格等資料。(像是處理 excel 就會用矩陣)
  • 記憶體配置可以是 row-major 或 column-major。
    • row-major：記憶體連續存放「同一列」的元素。
    • column-major：記憶體連續存放「同一行」的元素。

常會用的矩陣操作跟線性代數的差不多，相乘、轉置等等...

本來想寫詳細一點以及介紹對後面 PDLP 很重要的稀疏矩陣 (Sparse Matrix)，但身體很不舒服得先睡覺，只能改天補上了...

謝謝~

參考資料
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，《演算法導論》，碁峰資訊，2024 年
ChatGPT