Jaka jest złożoność czasowa różnych struktur danych?

Próbuję wymienić czasową złożoność operacji wspólnych struktur danych, takich jak tablice, drzewo wyszukiwania binarnego, sterta, lista połączona itp., A zwłaszcza mam na myśli Javę. Są bardzo częste, ale wydaje mi się, że niektórzy z nas nie są w 100% pewni dokładnej odpowiedzi. Każda pomoc, zwłaszcza referencje, jest bardzo mile widziana.

Np. Dla listy pojedynczo połączonej: Zmiana elementu wewnętrznego to O (1). Jak możesz to zrobić? Ty MASZ szukać element przed zmianą. Również w przypadku wektora dodanie elementu wewnętrznego jest podane jako O (n). Ale dlaczego nie możemy tego zrobić w zamortyzowanym stałym czasie przy użyciu indeksu? Proszę, popraw mnie, jeśli czegoś mi brakuje.

Jako pierwszą odpowiedź zamieszczam moje ustalenia / domysły.

Tablice

• Ustaw, sprawdź element pod określonym indeksem: O (1)
• Wyszukiwanie : O (n) jeśli tablica jest nieposortowana i O (log n) jeśli tablica jest posortowana i używane jest coś w rodzaju wyszukiwania binarnego,
• Jak zauważył Aivean , na tablicach nie jest Deletedostępna żadna operacja. Możemy symbolicznie usunąć element ustawiając mu określoną wartość np. -1, 0 itd. W zależności od naszych wymagań
• Podobnie Insertdla tablic jest w zasadzie Setjak wspomniano na początku

ArrayList:

• Dodaj : amortyzowane O (1)
• Usuń : O (n)
• Zawiera : O (n)
• Rozmiar : O (1)

Połączona lista:

• Wstawianie : O (1) , jeśli jest zrobione na początku, O (n) jeśli gdziekolwiek indziej, ponieważ musimy osiągnąć tę pozycję, przechodząc liniowo przez listę połączoną.
• Usuwanie : O (1) , jeśli zrobione na początku, O (n) jeśli gdziekolwiek indziej, ponieważ musimy osiągnąć tę pozycję, przechodząc liniowo przez listę połączoną.
• Wyszukiwanie : O (n)

Lista podwójnie połączona:

• Wstawianie : O (1) , jeśli wykonano na początku lub końcu, O (n) jeśli gdziekolwiek indziej, ponieważ musimy osiągnąć tę pozycję, przechodząc liniowo po liście połączonej.
• Usuwanie : O (1) , jeśli zrobione na początku lub końcu, O (n) jeśli gdziekolwiek indziej, ponieważ musimy osiągnąć tę pozycję, przechodząc liniowo przez listę połączoną.
• Wyszukiwanie : O (n)

Stos:

• Wciśnij : O (1)
• Pop : O (1)
• Góra : O (1)
• Szukaj (coś w rodzaju wyszukiwania, jako operacja specjalna): O (n) (chyba tak)

Queue / Deque / Circular Queue:

• Wstaw : O (1)
• Usuń : O (1)
• Rozmiar : O (1)

Drzewo wyszukiwania binarnego:

• Wstawianie, usuwanie i wyszukiwanie : Przypadek średni: O (log n) , Przypadek najgorszy: O (n)

Drzewo czerwono-czarne:

• Wstawianie, usuwanie i wyszukiwanie : Przypadek średni: O (log n) , Przypadek najgorszy: O (log n)

Heap / PriorityQueue (min / max):

• Znajdź Min / Znajdź Max : O (1)
• Wstaw : O (log n)
• Usuń Min / Usuń Max : O (log n)
• Wyodrębnij min / Wyodrębnij maks . : O (log n)
• Lookup, Delete (jeśli w ogóle podano): O (n) , będziemy musieli przeskanować wszystkie elementy, ponieważ nie są one uporządkowane jak BST

HashMap / Hashtable / HashSet:

• Wstaw / Usuń : O (1) amortyzowane
• Zmień rozmiar / hash : O (n)
• Zawiera : O (1)