第四週了各位！我們進入決賽圈啦！！

在深入演算法之前，我們必須先熟悉幾種基本且常見的資料結構。資料結構決定了資料的儲存和組織方式，直接影響我們如何存取、修改資料，進而左右演算法的設計方向和效率。

複雜度

關於演算法效能，我們經常提到兩個概念：時間複雜度和空間複雜度。讓我們用生活中的例子來理解這些概念：

空間複雜度

空間複雜度就像是完成任務需要的工作空間，簡單來說，就是指記憶體空間的使用量。

時間複雜度

時間複雜度就是指完成任務所需的執行時間，這也是大部分開發者較為重視的部分，畢竟時間就是最寶貴的資源，以下使用 Big O 表示法來說明三種常見的情形。

1. O(1)

想像你在找一本書。如果這本書就擺在你的桌上，不管桌上有多少雜物，你都能立刻找到它。這就像 O(1) 的操作 — 不論資料量多大，都是執行 1 次的運算。

2. O(n)

假設你需要在一疊沒有排序的考卷中，找出有你名字的那張。你可能得從第一張翻到最後一張。這就是 O(n) 的情況 — 處理時間與資料量成正比，也就是執行 n 次的運算。

3. O(log n)

假設你們正在玩猜數字遊戲，範圍是 1 到 100。每次猜測後，對方會告訴你猜高了還是猜低了。如果你每次都猜中間數字，相當於把範圍縮小一半，最多只需猜 7 次就能找到答案。這就是 O(log n) 的概念 — 隨著範圍增加，所需時間只是稍微提升，相當於執行了接近 n/2 次的運算。

理解了這些概念，我們就能更好地認識各種資料結構了！

常見的資料結構

接下來，我們將結合上述時間複雜度，介紹每種資料結構的搜尋、新增和刪除操作效率。

本次介紹不包含鏈結陣列、樹狀結構、圖形結構（因為沒太多實務經驗，不太熟悉XD）

陣列（Array）

陣列是最基本的資料結構之一，它在連續的記憶體位置儲存相同類型的元素。

時間複雜度：

• 搜尋（未排序陣列）：O(n)
• 搜尋（已排序陣列，使用二分搜尋）：O(log n)
• 新增（末尾）：O(1)
• 新增（開頭或中間）：O(n)
• 刪除（末尾）：O(1)
• 刪除（開頭或中間）：O(n)

雜湊表（Hash Table）

雜湊表利用雜湊函數將鍵映射到值，是一種高效的查詢結構，相當於英文字典，所有單字已經依據 26 個字母排列分類過。

時間複雜度（平均情況）：

• 搜尋：O(1)
• 新增：O(1)
• 刪除：O(1)

堆疊（Stack）

遵循後進先出（LIFO）的原則，就像疊盤子一樣。

時間複雜度：

• 搜尋：O(n)
• 新增（疊上新的盤子）：O(1)
• 刪除（丟掉最上面的盤子）：O(1)

佇列（Queue）

遵循先進先出（FIFO）的原則，就像排隊的隊伍一樣。

時間複雜度：

• 搜尋：O(n)
• 新增（加入隊伍）：O(1)
• 刪除（離開隊伍）：O(1)

如何選擇適當的資料結構？

選擇資料結構時，需要考量以下因素：

1. 常見操作類型（例如：頻繁的搜索、新增或刪除）
2. 資料的存取模式（隨機存取還是順序存取）
3. 記憶體使用限制
4. 資料量大小
5. 預期的資料增長趨勢

結語

今天介紹的每種資料結構都有其獨特的優勢和應用場景，接著在學習演算法時，你會發現這些資料結構常常是實作各種演算法的基礎，加油！