Verschiedene Datenstrukturen und Komplexitäten

Question

Ich weiß, dass wiki link existiert, die unterschiedliche Datenstrukturen hat.

Ich möchte wissen, ob es einen Ort gibt, wo ich die Komplexität (zum Einfügen, Löschen, Aktualisieren usw.) in einem sauberen Tabellenformat (als Referenz) bekommen kann.

Answer 1

Die Seite, mit der Sie in Ihrer Frage verknüpft haben, enthält eine Liste mit vielen Datenstrukturen. Jede von ihnen eine Seite, die die spezifischen Datenstrukturen beschreibt. Ich weiß, Sie wollen die Tabelle der Vergleiche in einem fertigen Format, aber da es nicht zu existieren scheint, könnte es etwas sein, das Sie leicht zusammenstellen können, indem Sie die verschiedenen Seiten durchblättern. Zum Beispiel ist der Vergleich der verschiedenen Algorithmen in dem Array und für den B-Baum here gegeben. Es kann also etwas Arbeit erfordern, alles zu einer einfachen Referenz zusammenzufassen. Hmmm ... vielleicht ist da ein Blogeintrag in Vorbereitung.

Answer 2

Hier ist es auf Wikipedia: 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.