利用MSDN文件找出Collections的時間複雜度
主題 |
利用MSDN文件找出Collections的時間複雜度 |
介紹 |
新手開發人員在挑選List、LinkedList、Dictionary...等Collections來裝載資料時，可能會挑選到不適當的Collections導致程式效能低落。可以利用MSDN文件找出Collections的時間複雜度，再以自己的情境需求挑選適合的Collections。 |
作者 |
姜志民 |
版本 |
1.0 |
產出日期 |
2017 / 02/ 09 |
1 目的
新手開發人員在挑選List、LinkedList、Dictionary...等Collections來裝載資料時，可能會挑選到不適當的Collections導致程式效能低落。可以利用MSDN文件找出Collections的時間複雜度，再以自己的情境需求挑選適合的Collections。
2 時間複雜度
執行完成程式所需要的時間就稱為時間複雜度，並以大O符號作為標記符號。下表是常見到的時間複雜度的等級，越往下等級所需要的時間就越多。
n為輸入量，O(1)是忽略輸入量的大小，不因為n的大小而影響時間。
O(1)： |
常數時間 |
O(log n)： |
次線性時間 |
O(n)： |
線性時間 |
O(n log n)： |
線性乘對數時間 |
O(n2)： |
平方時間 |
O(n3)： |
立方時間 |
O(2n)： |
指數時間 |
3 實戰-動手查查看(情境一：新增資料)
以List、LinkedList與Dictionary這三種的Collections來做範例，以「新增資料」情境模擬使用，假設新增輸入量n為10000。
Collections |
List<T>.Add |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/3wcytfd1(v=vs.110).aspx |
下列是MSDN文件的「註解」，假設List的Capacity是10，若加入資料數量為8
，則時間複雜度只有O(1)，但現要加入資料數量是10000，所以時間複雜度就變成O(10000)。
Collections |
LinkedList<T>.Add |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/ms132177(v=vs.110).aspx |
下列是MSDN文件的「註解」，O(1)是可以忽略輸入量的大小。
Collections |
Dictionary<TKey, TValue>.Add |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/k7z0zy8k(v=vs.110).aspx |
下列是MSDN文件的「註解」，假設Dictionary的Capacity是10，若加入資料數量為8，則時間複雜度只有O(1)，但現要加入資料數量是10000，所以時間複雜度就變成O(10000)。
4 實戰-動手查查看(情境二：搜尋資料)
以List、LinkedList與Dictionary這三種的Collections來做範例，以「搜尋資料」情境模擬使用，假設搜尋資料量n為10000。
Collections |
List<T>.Find |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/x0b5b5bc(v=vs.110).aspx |
下列是MSDN文件的「註解」，List.Find的時間複雜度是O(10000)。
Collections |
List<T>.BinarySearch |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/w4e7fxsh(v=vs.110).aspx |
下列是MSDN文件的「註解」，List.BinarySearch的時間複雜度是O(log 10000)。
Collections |
LinkedList<T>.Find |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/99a4073e(v=vs.110).aspx |
下列是MSDN文件的「註解」，LinkedList.Find的時間複雜度是O(10000)。
Collections |
Dictionary<TKey, TValue>.Item |
MSDN資料 |
https://msdn.microsoft.com/zh-tw/library/9tee9ht2(v=vs.110).aspx |
下列是MSDN文件的「註解」，Dictionary.Item的時間複雜度是O(1)。
5 情境整理
情境一：假設新增輸入量n為10000。
List<T>.Add |
LinkedList<T>.Add |
Dictionary<TKey, TValue>.Add |
|
時間複雜度 |
O(10000) |
O(1) |
O(10000) |
新增效能：LinkedList > List = Dictionary
情境二：假設搜尋資料量n為10000。
List.Find |
List.BinarySearch |
LinkedList.Find |
Dictionary.Item |
|
時間複雜度 |
O(10000) |
O(log 10000) |
O(10000) |
O(1) |
搜尋效能：Dictionary > List.BinarySearch > List.Find = LinkedList. Find
6 結論
不同情境挑對Collections會讓程式大大加分，除了選對Collections之外，method也要選對。List.BinarySearch與List.Find就是個好例子，一樣都是List的method，但卻有不同的時間複雜度，尤其在資料量非常大時，就可以明顯看出效能的差異。
