请说明 C# 中 List 和 Dictionary 等常见集合类型的典型操作（如查找、插入、删除）分别具有怎样的渐近时间复杂度？

回答思路

1. 【回答框架 1】List<T> 底层是动态数组，按索引访问为 O(1)，在末尾添加或删除通常为均摊 O(1)，但在中间插入或删除需要移动后续元素，时间复杂度为 O(n)。查找无重复值时线性搜索为 O(n)，使用 BinarySearch 需先排序，为 O(log n)。
2. 【回答框架 2】Dictionary<TKey,TValue> 基于哈希表实现，插入、删除和按键查找的平均时间复杂度为 O(1)，但最坏情况下（大量哈希冲突）可能退化到 O(n)。键的比较和哈希计算会影响常量因子，但渐近上仍为 O(1)。
3. 【回答框架 3】SortedList 和 SortedDictionary 提供有序存储，插入、删除和查找均为 O(log n)，分别基于数组二分查找和平衡树（红黑树）。Stack 和 Queue 的压入与弹出均为 O(1)。
4. 【回答框架 4】HashSet<T> 与 Dictionary 类似，提供 O(1) 的添加、删除和包含检查。LinkedList<T> 在已知节点处插入或删除为 O(1)，但按索引访问为 O(n)。实际性能还要考虑内存分配和缓存局部性。
5. 【回答框架 5】选择集合时，应根据主要操作类型决定：频繁按索引随机访问优先 List，频繁按键读写优先 Dictionary，需要有序遍历时使用 SortedDictionary 或 SortedList。
6. 【关键点 1】List 索引访问 O(1)，中间插入删除 O(n)
7. 【关键点 2】Dictionary 平均 O(1)，最坏 O(n)
8. 【关键点 3】SortedDictionary 操作 O(log n)
9. 【关键点 4】HashSet 提供 O(1) 集合操作
10. 【关键点 5】LinkedList 已知节点操作 O(1)，随机访问 O(n)
11. 【易错点 1】不要把 Dictionary 的 O(1) 视为绝对，哈希冲突会导致退化
12. 【易错点 2】忽略 List 在中间插入删除的 O(n) 成本
13. 【易错点 3】混用 List 与 Dictionary 时未考虑转换开销