Différentes structures de données et complexités

Question

Je sais que wiki link existe qui a différentes structures de données.

Je veux savoir s'il y a un endroit où je peux obtenir les complexités (pour l'insertion, la suppression, la mise à jour etc.) dans un format de table soigné (pour la référence).

Answer 1

La page à laquelle vous avez lié dans votre question contient une liste de nombreuses structures de données. Chacun d'entre eux une page qui détaille les structures de données spécifiques. Je sais que vous voulez la table des comparaisons dans un format prêt à l'emploi, mais comme il ne semble pas exister, alors il pourrait être quelque chose que vous pouvez mettre en place facilement en parcourant les différentes pages. Par exemple, la comparaison des différents algorithmes dans le tableau est donnée here, et pour le b-arbre here. Il peut donc être nécessaire de travailler pour tout compiler en une simple référence. Hmmm ... peut-être y a-t-il un billet de blog en devenir.

Answer 2

Ici, il est sur 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.