Diverse strutture dati e complessità

Question

So che questo wiki link esiste che ha diverse strutture di dati.

Voglio sapere se c'è un posto dove posso ottenere le complessità (per inserire, eliminare, aggiornare ecc.) In un formato tabella ordinato (per riferimento).

Answer 1

La pagina a cui hai collegato nella tua domanda ha un elenco di molte strutture di dati. Ognuno di loro una pagina che dettaglia le strutture dati specifiche. So che vuoi la tabella dei confronti in un formato già pronto, ma dal momento che non sembra esistere, potrebbe essere qualcosa che puoi mettere insieme sfogliando le varie pagine. Ad esempio il confronto tra i vari algoritmi dell'array è dato da here e per l'albero b here. Quindi potrebbe richiedere del lavoro per compilarlo tutto in un semplice riferimento. Hmmm ... forse c'è un post sul blog in preparazione.

Answer 2

Qui si trova su 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.