Θ – 等于
f ( n ) = Θ ( g ( n ) ) f(n) = Θ(g(n)) f(n)=Θ(g(n)) 即 f ( n ) = g ( n ) f(n)
= g(n) f(n)=g(n)
Ο – 小于等于(常用于计算最坏情况,作为时间复杂度上界)
f ( n ) = O ( g ( n ) ) f(n) = Ο(g(n)) f(n)=O(g(n)) 即 f ( n ) ≤ g ( n ) f(n)
≤ g(n) f(n)≤g(n)
ο – 小于
f ( n ) = ο ( g ( n ) ) f(n) = ο(g(n)) f(n)=ο(g(n)) 即 f ( n ) < g ( n ) f(n)
< g(n) f(n)<g(n)
Ω – 大于等于
f ( n ) = Ω ( g ( n ) ) f(n) = Ω(g(n)) f(n)=Ω(g(n)) 即 f ( n ) ≥ g ( n ) f(n)
≥ g(n) f(n)≥g(n)
ω – 大于
f ( n ) = ω ( g ( n ) ) f(n) = ω(g(n)) f(n)=ω(g(n)) 即 f ( n ) > g ( n )
f(n) > g(n) f(n)>g(n)
因此,T1(n)<=O(f(n))
T2(n)>=Ω(g(n))
f(n) > g(n)
两种算法并没有确切的复杂度范围。
不行。因为各种路径的 步数并不一定相同。
所有边权值加正数,只有在各种路径步数相同的情况下才可行。
Dijkstra 算法在运行过程中维持的关键信息是一组节点集合 S,从源节点 s 到
该集合中每个节点之间的最短路径已经被找到。算法重复从节点集合 V-S 中选
择最短路径估计最小的节点 u,将 u 加入到集合 S,然后对所有从 u 出发的边
进行松弛操作。
当把一个节点选入集合 S 时,即意味着已经找到了从源点到这个点的最短路径,
但若存在负权边,就与这个前提矛盾,可能会出现得出的距离加上负权后比已
经得到 S 中的最短路径还短。
当顶点 2 被收录、确定了最短路径之后,再收录顶点 3,以及边<2,3>,此时
顶点 2、3 之间的最短路径是 2->3,等遇到负值边<3,4>后就会发现,顶点
2、3 之间的最短路径其实是 2->4->3,但已收录的无法更新,即出现算法错
误。
原图的最短路为 1234
而增加了之后的最短路变成了 154
(1).用图模型建模: