summary of time complexity for common data structures

常見資料結構之平均時間複雜度
=======================

運算之平均時間複雜度        新增       刪除      查詢
--限特定位置增刪查詢之線性容器--
陣列堆疊(尾入尾出)          O(1)       O(1)      O(1)
鏈結堆疊(頭入頭出)          O(1)       O(1)      O(1)
陣列佇列(環狀尾入頭出)      O(1)       O(1)      O(1)
鏈結佇列(尾入頭出)          O(1)       O(1)      O(1)
陣列雙邊佇列(環狀頭尾出入)  O(1)       O(1)      O(1)
鏈結雙邊佇列(雙向頭尾出入)  O(1)       O(1)      O(1)

--線性容器--
無序陣列清單                O(1)       O(n)       O(n)
無序鏈結清單                O(1)       O(n)       O(n)
有序陣列清單                O(n)       O(n)       O(log(n))
有序鏈結清單                O(n)       O(n)       O(n)
雜湊表                      O(1)       O(1)       O(1)

--非線性容器--
二分搜索樹                  O(log(n))  O(log(n))  O(log(n))
跳躍鏈結清單                O(log(n))  O(log(n))  O(log(n))
堆積(限頭才能刪除,查詢)     O(log(n))  O(log(n))  O(1)

參考:
1.carrano-pie-05-data abstraction & problem solving with java
2.weiss-pie-04-data structures & problem solving using java
3.budd-awl-00-classic data structures in java

time complexity for sorting algorithms

時間複雜度             最差        平均
選擇排序              O(n2)       O(n2)
氣泡排序              O(n2)       O(n2)
插入排序              O(n2)       O(n2)
快速排序              O(n2)       O(n*log(n))
樹形排序              O(n2)       O(n*log(n))
合併排序              O(n*log(n))  O(n*log(n))
堆積排序              O(n*log(n))  O(n*log(n))
謝耳排序              O(n1.5)     O(n1.25)
數元排序(限整數)      O(n)         O(n)

參考:
1.carrano-pie-05-data abstraction & problem solving with java
2.weiss-pie-04-data structures & problem solving using java
3.budd-awl-00-classic data structures in java