m**********e
发帖数: 220 | 1 Dijkstra 算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合 Q，所
以搜索 Q 中最小元素的咚悖‥xtract-Min(Q)）只需要線性搜索 Q 中的所有元素。這
樣的話算法的咝袝r間是 O(n2)。
这是维基百科上看到的
我想问一下就是为什么算法复杂度是O(n2呢， 每次搜到最小元素以后就删除，放到另
一个链表里，这样下一次不就是ｎ减一了吗？ 应该是ｏ(n!)啊
不是吗
谢谢 |
z*******3
发帖数: 13709 | |
m**********e
发帖数: 220 | 3 为什么？
【在 z*******3 的大作中提到】
: ………………………………
: 跪了
|
d**o
发帖数: 864 | 4 最差情况遍历所有点，每一次又遍历Q中元素查找最小，所以是O(n^2)
不明白O(n!)什么意思，你想说的是O(n(n-1))吗？这就是O(n^2)
【在 m**********e 的大作中提到】
: Dijkstra 算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合 Q，所
: 以搜索 Q 中最小元素的咚悖‥xtract-Min(Q)）只需要線性搜索 Q 中的所有元素。這
: 樣的話算法的咝袝r間是 O(n2)。
: 这是维基百科上看到的
: 我想问一下就是为什么算法复杂度是O(n2呢， 每次搜到最小元素以后就删除，放到另
: 一个链表里，这样下一次不就是ｎ减一了吗？ 应该是ｏ(n!)啊
: 不是吗
: 谢谢
|
c*********e
发帖数: 16335 | 5 en,每种算法其实都有best case,worst case.所以，每种算法其实有好几个big o
notation值。
【在 d**o 的大作中提到】
: 最差情况遍历所有点，每一次又遍历Q中元素查找最小，所以是O(n^2)
: 不明白O(n!)什么意思，你想说的是O(n(n-1))吗？这就是O(n^2)
|
m**********e
发帖数: 220 | 6 我想说的是ｎ的阶乘啊
因为每次都把最小的元素删除了，这样总元素的个数就是ｎ-1了
难道不对吗
【在 d**o 的大作中提到】
: 最差情况遍历所有点，每一次又遍历Q中元素查找最小，所以是O(n^2)
: 不明白O(n!)什么意思，你想说的是O(n(n-1))吗？这就是O(n^2)
|
t****t
发帖数: 6806 | 7 i guess you didn't even get the algorithm right...
【在 m**********e 的大作中提到】
: 我想说的是ｎ的阶乘啊
: 因为每次都把最小的元素删除了，这样总元素的个数就是ｎ-1了
: 难道不对吗
|
d**o
发帖数: 864 | 8 你想说的是和不是乘吧？
即使是这样，复杂度的O表示法还是O(n^2)
【在 m**********e 的大作中提到】
: 我想说的是ｎ的阶乘啊
: 因为每次都把最小的元素删除了，这样总元素的个数就是ｎ-1了
: 难道不对吗
|
c*********e
发帖数: 16335 | 9 Dijkstra 算法的時間複雜度是 (n-1) + (n-2) +(n-3)...+1,時間複雜度是o(n2).
【在 m**********e 的大作中提到】
: Dijkstra 算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合 Q，所
: 以搜索 Q 中最小元素的咚悖‥xtract-Min(Q)）只需要線性搜索 Q 中的所有元素。這
: 樣的話算法的咝袝r間是 O(n2)。
: 这是维基百科上看到的
: 我想问一下就是为什么算法复杂度是O(n2呢， 每次搜到最小元素以后就删除，放到另
: 一个链表里，这样下一次不就是ｎ减一了吗？ 应该是ｏ(n!)啊
: 不是吗
: 谢谢
|
m**********e
发帖数: 220 | 10 嗯。。写错了
是和
我懂了
谢谢大家
还想问一下就是我的图是用邻接表存储的，但算法就是用普通方法实现的
看到网上说有办法可以改进算法，對於邊數少於 n2 的稀疏圖來說，我們可以用鄰接表
來更有效的實現该算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最
小的頂點（Extract-Min）。當用到二叉堆的時候，算法所需的時間為O((m + n)log n)
，斐波納契堆能稍微提高一些性能，讓算法咝袝r間達到O(m + n log n)。
不是很懂怎样用二叉堆来做这个算法
【在 d**o 的大作中提到】
: 你想说的是和不是乘吧？
: 即使是这样，复杂度的O表示法还是O(n^2)
|
