鄰接矩陣和鄰接表的時間/空間複雜度

Question

我正在閱讀Eva Tardos的「算法設計」，並在第3章中提到鄰接矩陣的複雜度爲O(n^2)，而鄰接列表的數量爲O(m+n)，其中m是總數邊和n是節點的總數。它說，在鄰接列表的情況下，我們只需要每個節點的大小爲m的列表。

因爲我們有列表，它們也是一維數組，所以在鄰接列表的情況下，我們不會得到類似於矩陣的東西嗎？據我所知，基本上是O(m*n)。請指導我。

Answer 1

鄰接關係矩陣爲每對節點保留一個值（1/0），無論邊是否存在，因此它需要n*n空間。

毗鄰列表只包含現有的邊緣，所以它的長度至多是邊緣的數量（或邊緣數量少於節點的節點數量）。

它說，在相鄰列表的情況下，我們將只需要每個節點的大小爲 m的列表。

我想你誤解了那部分。一個鄰接表不是保存一個大小爲m的列表每節點，因爲m是整體的邊數。

在完全連接的圖中，每對節點之間存在邊緣，因此鄰接列表和矩陣都需要空間的n*n，但對於其他情況 - 鄰接列表將更小。