Różne struktury danych i Złożoność

Question

wiem to wiki link istnieje który ma różne struktury danych.

Chcę wiedzieć, czy jest to miejsce, gdzie mogę dostać zawiłości (na wstawianie, usuwanie, aktualizacja itp) w czystym formacie tabeli (dla porównania).

Answer 1

Strona, którą związana w swoim pytaniu ma listę wielu struktur danych. Każda z nich to strona, która szczegółowo określa określone struktury danych. Wiem, że chcesz tabelę porównań w gotowym formacie, ale ponieważ wydaje się, że nie istnieje, może to być coś, co możesz łatwo złożyć, przeglądając różne strony. Na przykład porównanie różnych algorytmów w tablicy podano here, a dla b-drzewa here. Więc może wymagać trochę pracy, aby skompilować to wszystko w prosty odnośnik. Hmmm ... może jest wpis na blogu.

Answer 2

Tu jest na Wikipedii: 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.