Jaka jest złożoność czasowa indeksowania, wstawiania i usuwania z typowych struktur danych?

Question

Nie ma dostępnego podsumowania dużej notacji O do operacji na najpopularniejszych strukturach danych, w tym tablicach, połączonych listach, tabelach mieszających itp.

Answer 1

Domyślam się, że zacznę od złożoności czasowej połączonej listy:

indeksowania ----> o (n)
wstawiania/usuwania w celu ----> o (1) lub o (n)
wstawiania/usuwania w środkowy ---> o (1) z iteratorem O (n) bez kompresji

Złożoność czasu dla wstawiania na końcu dep kończy się, jeśli masz lokalizację ostatniego węzła, jeśli to zrobisz, będzie to O (1) w przeciwnym razie będziesz musiał przeszukać listę połączoną, a złożoność czasu przeskoczy do O (n).

Answer 2

zamortyzowanego Big-O dla hashtables:

• Insert - O (1)
• Pobierz - O (1)
• Usuń - O (1)

Należy pamiętać, że istnieje jest stałym czynnikiem dla algorytmu mieszającego, a amortyzacja oznacza, że ​​rzeczywista zmierzona wydajność może się znacznie różnić.

Answer 3

Red-Black drzew:

• Insert - O (log n)
• Pobierz - O (log n)
• Usuń - O (log n)

Answer 4

Należy pamiętaj, że jeśli nie piszemy własnej struktury danych (np. połączonej listy w C), może ona dramatycznie zależeć od implementacji struktur danych w wybranym języku/strukturze. Jako przykład, spójrz na benchmarks of Apple's CFArray over at Ridiculous Fish. W tym przypadku typ danych, CFArray z CoreFoundation firmy Apple, faktycznie zmienia struktury danych w zależności od tego, ile obiektów faktycznie znajduje się w tablicy - zmieniając od liniowego czasu do stałego czasu na około 30 000 obiektów.

To jest rzeczywiście jednym z najpiękniejszych rzeczy na temat programowania obiektowego - nie trzeba znać jak działa tylko że to działa, a „jak to działa” może się zmieniać w zależności od wymagań .

Answer 5

Informacja na ten temat jest już dostępna na Wikipedii pod adresem: Search data structure

+----------------------+----------+------------+----------+--------------+ 
|      | 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.