赞
踩
上一篇Dijkstra算法伪代码第7行:在每次刷新d(v)之后,找出最小的d(v),这个地方具体用什么方法是没有说的,不同的找最小的方法和所涉及的数据结构的时间复杂度也是不一样的。
最直接暴力的思路就是一个for循环遍历找出最小的d(v),但时间复杂度太高,需要遍历所有点,总的时间复杂度就是
O
(
n
2
)
O(n^2)
O(n2),点很多的时候,这个算法就很慢了。
因此,我们需要在如何找最小值这进行优化。
我们来看一下存储d(v)的数据结构需要支持什么。在Dijkstra算法中,需要支持可以insert一个值、extract最小值、upadte一个值、delete一个值,而且需要动态调整变化的大小顺序。
优先队列(Priority Queue,PQ)可以满足上面的需求。
常见的优先队列应用场景:
Dijkstra’s shortest path algorithm
Prim’s MST algorithm
Huffman coding
A∗ searching algorithm
HeapSort
…
采用优先队列来存储d(v)值,即PQ集合(优先级就是node对应的d(v)值,后面统一用key(v)),一开始构造队列的插入操作要执行n次,获取最小key(v)在循环中要n次,更新队列中key(v)要m次(m是边的数量),更新了key(v)后可能需要调整队列。(ExtractMin包含取最小值和从队列中删除两个操作)
伪代码如下:
通过分析,我们发现主要影响该算法时间复杂度的是队列的三个操作Insert,ExtractMin,DecreaseKey,如果我们构成优先队列用的是普通的无序数组或链表,那么每次Insert的复杂度就只有O(1),但ExtractMin就要O(n)(每次都要遍历数组、链表),如果是有序数组或链表,Insert需要O(n)(遍历查找合适插入位置),ExtractMin只用O(1)。所以选择不同的数据结构构造队列,会导致算法时间复杂度不同。下表列出了四种实现队列的不同数据结构方式:
一般实际问题中边的数量m>点的数量n
最小堆就是任意一个节点的值总是小于等于其孩子节点的值,且堆必须是完全二叉树。实现可以通过链表或数组两种方式。
我们重点看看Dijkstra算法涉及的三个操作,为什么最小堆可以降低这三个操作时间复杂度?
举例:Insert(7)
举例:ExtractMin()
举例:DecreaseKey( ptr, 7 )
合起来,利用最小堆实现优先队列的时间复杂度是:
O
(
n
∗
l
o
g
n
(
n
次
I
n
s
e
r
t
)
+
n
∗
l
o
g
n
(
n
次
E
x
t
r
a
c
t
M
i
n
)
+
m
∗
l
o
g
n
(
m
次
D
e
c
r
e
a
s
e
K
e
y
)
)
=
O
(
m
l
o
g
n
)
O(n*logn(n次Insert) + n*logn(n次ExtractMin)+m*logn(m次DecreaseKey))= O(mlogn)
O(n∗logn(n次Insert)+n∗logn(n次ExtractMin)+m∗logn(m次DecreaseKey))=O(mlogn)
二项堆在二叉堆的基础上优化了合并堆耗费的时间(从O(n)到O(logn))。
二叉堆采用单棵树的方式存储,而在二项堆中采用多棵树表示。
二项树的定义:
举例:下图是多颗二项树,看起来长得很歪,但其实长得很正。我们按顺序,每棵分层看,就是二项式、杨辉三角,这也就是为什么叫做二项树的原因。
1
1 1
1 2 1
1 3 3 1
而二项堆由多个二项树构成(森林),将只含一个节点的二项树称作
B
0
B_0
B0 ,将两个
B
0
B_0
B0组合成的二项树称作
B
1
B_1
B1,以此类推。把每棵二项树的根节点用链表连起来就是二项堆。(B就是级别)
一个堆中不能有两个一样级别的树,如果一个堆中出现两棵级别一样的树,就将它们合并。因此一个二项堆中若容纳n棵树,合并过后最多只会有 l o g 2 n + 1 log_2 n+1 log2n+1棵树,最高树的高度是 l o g 2 n log_2 n log2n。
我们简单分析一下二项堆时间复杂度:
可以发现,二项堆相比二叉堆,降低了Union操作的时间复杂度。
二项堆Insert和Union的时间是logn,事实上,我们还可以进一步确定其时间复杂度可以到达O(1)。
我们来看个例子,当上一次发生多次合并耗费O(logn)的时间之后,下一次只耗费O(1)的时间。
假设某一次耗费O(logn)了,在这之后不断插入元素的时间消耗,显然有O(1),O(2),O(1),O(3),O(1)…我们发现,在很长一段时间内,插入耗费的时间都是常数阶的。因此,我们不能单一地根据一次时间消耗是O(logn)而断言时间复杂度是O(logn),需要考虑一串操作的整体期望时间复杂度。通过均摊分析可以证明是O(1)。
谈到了优先队列,引入了两个新的数据结构:二叉堆与二项堆,它们的设计是我们在算法设计过程中的另一种优化,从数据结构上优化算法。
我们从一开始使用线性链表实现优先队列,发现求最小太慢,改为有序链表,发现插入太慢,然后变成部分有序,采用二叉堆,然后从只用一颗树变成多棵树的二项堆,逐步放松了限制条件,减少了许多冗余计算,优化了问题。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。