異なるデータ構造と複雑さ

Question

私はこれを知っていますwiki linkが存在し、データ構造が異なります。

（参照用に）きちんとした表形式で複雑（挿入、削除、更新など）ができる場所があるかどうかを知りたいです。

Answer 1

質問にリンクしたページには、多数のデータ構造のリストがあります。それぞれのページには、特定のデータ構造の詳細が記載されています。私はあなたが比較可能な形式で比較表を望むのを知っていますが、存在しないように見えるので、さまざまなページをブラウズすることで簡単にまとめることができます。たとえば、配列内のさまざまなアルゴリズムの比較にはhere、b-treeの場合は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.