Struktury danychmedium

Lista sąsiedztwa vs macierz sąsiedztwa — kiedy którą wybrać?

Tagi

#graph#adjacency-list#adjacency-matrix#complexity

Odpowiedź

Macierz zajmuje O(V^2) pamięci i daje O(1) sprawdzenie krawędzi, więc jest dobra dla gęstych grafów. Lista zajmuje O(V+E) pamięci i lepiej pasuje do rzadkich grafów oraz iterowania po sąsiadach.

Powiązane pytania

Struktury danych

Lista sąsiedztwa vs macierz sąsiedztwa: kiedy wybrać które?

#graph#adjacency-list#adjacency-matrix

Struktury danych

Budowanie kopca z tablicy: dlaczego może być O(n), a nie O(n log n)?

#heap#heapify#complexity

Algorytmy

Heap sort: jaka jest złożoność czasowa, pamięciowa i stabilność?

#heapsort