大家好，又见面了，我是你们的朋友全栈君。
之前一直默认Dijkstra算法时间复杂度为
o ( n 2 ) o(n^{2}) o(n2)，没有思考过具体的时间复杂度，今天把这个弄清楚。
Dijkstra算法的思路与关键点
- 思路：广度优先 + 松弛
- 所有点分为两个集合 S S S和 T T T， S S S最开始只包括源点 s s s，剩余点都位于 T T T。 S S S集合表示已经计算出最短路径的点集合， T T T表示尚未计算出最短路径的点集合。
- 每次从集合 T T T中选出一个与集合 S S S距离最短的点 v v v，将点 v v v加入集合 S S S。通过点 v v v对集合 T T T中的点进行松弛，即更新 T T T中点的最短距离。
- 不断重复此步骤2，直至T集合中无法找出与集合 S S S相邻的点。
- 关键点：每次从 T T T中选出的点，距离源点的距离一定不会被松弛，因此每次选出的点都将加入集合 S S S.。
Dijkstra算法的时间复杂度
设图中的节点数为 n n n，边个数为 m m m，平均每个点的边数 k = m / n k=m/n k=m/n
算法步骤2需要执行 n − 1 n-1 n−1次，每次从集合 T T T中选出一个与集合 S S S相距最近的点，具体实现方式有4种。
- 顺序遍历集合 T T T
- 使用二叉堆作为优先队列
- 使用二项堆作为优先队列
- 使用斐波那契堆作为优先队列
前提知识：二叉堆，二项堆，斐波那契堆的各种操作时间复杂度
对于Dijkstra算法，给出时间复杂度的计算公式
( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) (n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) (n−1)∗(TEXTRACT−MIN+TDELETE+TDECREASE−KEY∗k)
下面对于上述四种方式，分别计算其时间复杂度。
- 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( n + 1 + k ) = n ∗ ( n + k ) = n 2 + m = n 2 \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(n+1+k)\\ &=n*(n+k)\\ &=n^{2}+m &=n^{2} \end{aligned} 时间复杂度=(n−1)∗(TEXTRACT−MIN+TDELETE+TDECREASE−KEY∗k)=(n−1)∗(n+1+k)=n∗(n+k)=n2+m=n2
- 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( 1 + log n + k ∗ log ( n ) ) = n ∗ ( 1 + k ) log n = ( n + m ) log n \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(1+\log{n}+k*\log(n))\\ &=n*(1+k)\log{n}\\ &=(n+m)\log{n} \end{aligned} 时间复杂度=(n−1)∗(TEXTRACT−MIN+TDELETE+TDECREASE−KEY∗k)=(n−1)∗(1+logn+k∗log(n))=n∗(1+k)logn=(n+m)logn
- 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( log n + log n + k ∗ log ( n ) ) = n ∗ ( 2 + k ) log n = ( 2 n + m ) log n = ( n + m ) log n \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(\log{n}+\log{n}+k*\log(n))\\ &=n*(2+k)\log{n}\\ &=(2n+m)\log{n}\\ &=(n+m)\log{n} \end{aligned} 时间复杂度=(n−1)∗(TEXTRACT−MIN+TDELETE+TDECREASE−KEY∗k)=(n−1)∗(logn+logn+k∗log(n))=n∗(2+k)logn=(2n+m)logn=(n+m)logn
- 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( log n + log n + k ∗ 1 ) = n ∗ ( 2 log n + k ) = 2 n log n + m = n log n + m \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(\log{n}+\log{n}+k*1)\\ &=n*(2\log{n}+k)\\ &=2n\log{n}+m\\ &=n\log{n}+m\\ \end{aligned} 时间复杂度=(n−1)∗(TEXTRACT−MIN+TDELETE+TDECREASE−KEY∗k)=(n−1)∗(logn+logn+k∗1)=n∗(2logn+k)=2nlogn+m=nlogn+m
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/146452.html原文链接：https://javaforall.net
