對於一個家庭作業問題,我被問到給定一組n個節點和m個邊的問題,其中圖由鄰接列表表示,爲什麼insertVertex將採用O(1),deleteVertex將採取O (M)。時間複雜度/圖論
我不完全確定我的答案,但我把那個insertVertex是O(1),因爲當你第一次插入時,你添加到數組的所有元素都是一個節點和一組相鄰的頂點(意思是你的頂點新節點指向)。因此這個時間複雜度是不變的。但是,在刪除節點時,不僅必須刪除節點和節點附帶的相鄰邊,還必須通過其餘的m邊來確保刪除指向節點的節點和邊你試圖刪除的節點(因爲你不能指向沒有任何邊緣)
我是新來的圖論,所以我不知道我的思維方式是否正確。是巨大的。
感謝
聽起來像對我堅實的推理,但我敢打賭,別人在這裏可以澄清更多。 –