不同的數據結構和複雜性

Question

我知道這wiki link存在具有不同的數據結構。

我想知道是否有一個地方，我可以得到一個整潔的表格格式（供參考）的複雜性（插入，刪除，更新等）。

Answer 1

您在問題中鏈接到的頁面有許多數據結構的列表。他們每個人都有一個詳細介紹具體數據結構的頁面。我知道你想要一個現成的格式比較表，但由於它看起來不存在，所以它可能是你可以輕鬆地通過瀏覽各種頁面放在一起的東西。例如，陣列中的各種算法的比較給出here，並且對於b樹here給出。所以它可能需要一些工作來將它們編譯成一個簡單的參考。嗯......也許有一個博客文章正在製作中。

Answer 2

這是維基百科：Worst-case analysis of data structures

+----------------------+----------+------------+----------+--------------+ 
|      | Insert | Delete | Search | Space Usage | 
+----------------------+----------+------------+----------+--------------+ 
| Unsorted array  | O(1)  | O(1)  | O(n)  | O(n)   | 
| Value-indexed array | O(1)  | O(1)  | O(1)  | O(n)   | 
| Sorted array   | O(n)  | O(n)  | O(log n) | O(n)   | 
| Unsorted linked list | O(1)* | O(1)*  | O(n)  | O(n)   | 
| Sorted linked list | O(n)* | O(1)*  | O(n)  | O(n)   | 
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n)   | 
| Heap     | O(log n) | O(log n)** | O(n)  | O(n)   | 
| Hash table   | O(1)  | O(1)  | O(1)  | O(n)   | 
+----------------------+----------+------------+----------+--------------+ 

* The cost to add or delete an element into a known location in the list 
    (i.e. if you have an iterator to the location) is O(1). 
    If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.