C#各种集合操作的性能总结

一、集合操作的性能特点标记说明：

1. O(1)：表示无论集合中有多少项，该操作所需的时间都不变。例如，ArrayList的Add()方法，无论集合大小如何，在列表尾部添加新元素的时间都是相同的。

2. O(n)：表示对于集合中的每个元素，需要增加的时间量都是相同的。如果集合需要重新分配内存，ArrayList的Add()方法就会变成O(n)，改变容量时，需要复制列表，复制的时间随元素的增加而线性增加。

二、各种集合的操作时间对比：

| 集合 | Add | Insert | Remove | Item | Sort | Find |

| | | | | | | |

| List<T> | 如果集合必须重置大小就是O(1)或O(n) | O(n) | O(n) | O(1) | O(n log n)（最坏情况O(n^2)） | O(n) |

| Stack<T> | Push()：如果栈必须重置大小，就是O(1)或O(n) | 不支持此操作 | Pop()：O(1) | 不支持此操作 | 不支持此操作 | 不支持此操作 |

| Queue<T> | Enqueue()：如果栈必须重置大小，就是O(1)或O(n) | 不支持此操作 | Dequeue()：O(1) | 不支持此操作 | 不支持此操作 | 不支持此操作 |

| HashSet<T> | Add()：O(1)或O(n)（取决于哈希表的性能）其他操作时间复杂度视具体实现而定。请注意，HashSet不支持排序和索引操作。 | | | | | |