C# 集合操作效能大全：Big-O 複雜度對照表與選型指南

Big-O 符號快速複習

• O(1)：常數時間，與資料量無關。
• O(n)：線性時間，隨資料量成比例增長。
• O(log n)：對數時間，資料量倍增，耗時僅增加常數。

主流集合操作複雜度對照表

* 可能觸發擴容，擴容為 O(n)。

選型決策樹

1. 需索引隨機存取、頻繁尾端新增 → List<T>
2. 先進先出（FIFO） → Queue<T>
3. 後進先出（LIFO） → Stack<T>
4. 唯一值集合、快速查重 → HashSet<T>
5. 頻繁中間插入/刪除、不需索引 → LinkedList<T>
6. 鍵值對、快速查找 → Dictionary<TKey,TValue>
7. 鍵值對且需有序枚舉 → SortedDictionary<TKey,TValue>（紅黑樹，插入較快）
8. 資料量小、頻繁索引存取有序鍵值 → SortedList<TKey,TValue>（陣列二分搜尋）

實務補充

• List<T> 預設容量 0，已知大概筆數時用建構子指定 new List<T>(capacity) 避免多次擴容。
• Dictionary 使用雜湊表，GetHashCode 與 Equals 實作品質直接影響效能。
• 避免在 foreach 中修改集合，改用 for 反向迴圈或 RemoveAll。
• .NET 6+ 新增 FrozenSet<T>、FrozenDictionary<TKey,TValue> 唯讀高效能查找。

總結

理解各集合的底層資料結構（動態陣列、雜湊表、紅黑樹、雙向鏈表）即可推導複雜度。實務上「先正確、再測量、最後優化」，依實際資料量與存取模式選型，比死記複雜度更有效。