作者LeoSW (易─雪)
看板b95902HW
标题[讨论] 演算法课的 Adjacency List
时间Tue Mar 11 14:07:43 2008
大家好
因为对於Adjacency List的部份有点不太了解
所以想请问一下各位
在老师的投影片里面
有关Adjacency List 来表示Graph的Data Structure里面
其中：
Insertion 需要 O(1) 的时间
Deletion 需要 O(1) 的时间
Query 需要 O(deg) 的时间
Query 需要 O(deg) 这个可以理解
只要将某一个List Linear Search 即可
Insertion 需要 O(1) 如果只是往後接那就是O(1)的时间内可以完成
可是Deletion 可以在O(1)的时间以内做完
是怎麽处理的呢？
有请教大家了
谢谢罗~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.43
1F：推 gglk:好像有听到老师说: 如果我们知道要删的对象是被哪个POINTER 03/11 17:48
2F：→ gglk:指到，就是O(1)，否则可能还需要搜一遍，也就是O(n) 03/11 17:48
3F：→ gglk:有错请原谅 03/11 17:50
4F：推 angela7736:听到跟楼上一样的话 03/11 18:00
5F：→ LeoSW:如果还要搜寻应该是O(deg)吧？ 03/11 20:29
6F：推 gglk:谢谢 O(deg) 03/11 22:22
7F：→ LeoSW:感谢两位解答~ 03/12 10:42