常用数据结构的时间复杂度
程序的复杂度分为时间复杂度和空间复杂度,通过字面上可以看出它们的含义,下面我们主要来看一个集合的时间复杂度,这些集合基本包含了.net里的所有了,呵呵!
| Data Structure | Add | Find | Delete | GetByIndex |
| Array (T[]) | O(n) |
O(n) |
O(n) |
O(1) |
| Linked list (LinkedList<T>) | O(1) |
O(n) |
O(n) |
O(n) |
| Resizable array list (List<T>) | O(1) |
O(n) |
O(n) |
O(1) |
| Stack (Stack<T>) | O(1) |
- |
O(1) |
- |
| Queue (Queue<T>) | O(1) |
- |
O(1) |
- |
| Hash table (Dictionary<K,T>) | O(1) |
O(1) |
O(1) |
- |
| Tree-based dictionary (SortedDictionary<K,T>) |
O(log n) |
O(log n) |
O(log n) |
- |
| Hash table based set (HashSet<T>) | O(1) |
O(1) |
O(1) |
- |
| Tree based set (SortedSet<T>) | O(log n) |
O(log n) |
O(log n) |
- |
如何选择数据结构
Array (T[])
- 当元素的数量是固定的，并且需要使用下标时。
Linked list (LinkedList<T>)
- 当元素需要能够在列表的两端添加时。否则使用 List<T>。
Resizable array list (List<T>)
- 当元素的数量不是固定的，并且需要使用下标时。
Stack (Stack<T>)
- 当需要实现 LIFO（Last In First Out）时。
Queue (Queue<T>)
- 当需要实现 FIFO（First In First Out）时。
Hash table (Dictionary<K,T>)
- 当需要使用键值对（Key-Value）来快速添加和查找，并且元素没有特定的顺序时。
Tree-based dictionary (SortedDictionary<K,T>)
- 当需要使用键值对（Key-Value）来快速添加和查找，并且元素根据 Key 来排序时。
Hash table based set (HashSet<T>)
- 当需要保存一组唯一的值，并且元素没有特定顺序时。
Tree based set (SortedSet<T>)
- 当需要保存一组唯一的值，并且元素需要排序时。
鸣谢
本文原文由Dennis Gao 发表自博客园,本人只是收藏之
本文章来自:http://www.cnblogs.com/gaochundong/p/3813252.html
相关参考资料:
本文转自博客园张占岭（仓储大叔）的博客，原文链接：数据结构～时间复杂度，如需转载请自行联系原博主。
