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

沒有留言:

Installing Code::Blocks on Windows for APCS Preparation

APCS 為大學程式設計先修檢測 (Advanced Placement Computer Science),其檢測等級可供大學個人申請入學時,比對是否符合各電腦相關科系APCS組申請資格之用。其中,針對 C 及 C++ 程式檢測者,考場提供 Linux 環境的輕量級 Code...

總網頁瀏覽量