2011-12-07 111 views
4

對於一個家庭作業問題,我被問到給定一組n個節點和m個邊的問題,其中圖由鄰接列表表示,爲什麼insertVertex將採用O(1),deleteVertex將採取O (M)。時間複雜度/圖論

我不完全確定我的答案,但我把那個insertVertex是O(1),因爲當你第一次插入時,你添加到數組的所有元素都是一個節點和一組相鄰的頂點(意思是你的頂點新節點指向)。因此這個時間複雜度是不變的。但是,在刪除節點時,不僅必須刪除節點和節點附帶的相鄰邊,還必須通過其餘的m邊來確保刪除指向節點的節點和邊你試圖刪除的節點(因爲你不能指向沒有任何邊緣)

我是新來的圖論,所以我不知道我的思維方式是否正確。是巨大的。

感謝

+0

聽起來像對我堅實的推理,但我敢打賭,別人在這裏可以澄清更多。 –

回答

3

O(m)的解釋是正確的。

如果你根據鏈表操作來解釋操作,你的解釋會更好。花費O(1)時間將節點追加到鏈表中。並且需要O(n)時間來刪除項目。

a)爲什麼insertVertex是O(1)?

插入頂點只是將節點附加到鏈接列表(O(1))或2(如果圖形是無向的)。

b)爲什麼deleteVertex是O(m)?

刪除頂點表示:

1)刪除鏈表(O(1))

2)在最壞的情況下,你必須從所有鏈接的列表中刪除頂點:O(米)。它是O(m)導致所有鏈表中的節點數是m,或者如果圖是無向的,則爲2 * m。

1

insertVertex花費O(1),因爲您只需添加一個新的元素,你的數據結構的結束。

deleteVertex需要O(m),因爲對於每一個邊,你必須檢查邊是否指向或從頂點指向(如果G指向)。

看起來你已經有了這個主意,但是,閱讀你的OP。