Diferentes estructuras de datos y Complejidades

Question

Sé que este wiki link existe que tiene diferentes estructuras de datos.

Quiero saber si hay un lugar donde pueda obtener las complejidades (para insertar, eliminar, actualizar, etc.) en un formato de tabla limpio (como referencia).

Answer 1

La página a la que se vinculó en su pregunta tiene una lista de muchas estructuras de datos. Cada una de ellas es una página que detalla las estructuras de datos específicas. Sé que quiere la tabla de comparaciones en un formato listo pero, como parece que no existe, podría ser algo que pueda armar fácilmente navegando por las distintas páginas. Por ejemplo, la comparación de los diversos algoritmos en la matriz se da here, y para el árbol b here. Por lo tanto, puede requerir algo de trabajo recopilarlo todo en una referencia simple. Hmmm ... tal vez haya una publicación de blog en proceso.

Answer 2

Aquí está en 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.