Dijkstra算法时间复杂度分析[通俗易懂]

Dijkstra算法时间复杂度分析[通俗易懂]文章目录Dijkstra算法的思路与关键点Dijkstra算法的时间复杂度之前一直默认Dijkstra算法时间复杂度为o(n2)o(n^{2})o(n2),没有思考过具体的时间复杂度,今天把这个弄清楚。Dijkstra算法的思路与关键点思路:广度优先+松弛所有点分为两个集合SSS和TTT,SSS最开始只包括源点sss,剩余点都位于TTT。SSS集合表示已经计算出最短路径的点集合,TTT表示尚未计算出最短路径的点集合。每次从集合TTT中选出一个与集合SSS距离最短的点vvv,将点vvv加

大家好,欢迎来到IT知识分享网。

之前一直默认Dijkstra算法时间复杂度为
o ( n 2 ) o(n^{2}) o(n2),没有思考过具体的时间复杂度,今天把这个弄清楚。

Dijkstra算法的思路与关键点

  • 思路:广度优先 + 松弛
  1. 所有点分为两个集合 S S S T T T S S S最开始只包括源点 s s s,剩余点都位于 T T T S S S集合表示已经计算出最短路径的点集合, T T T表示尚未计算出最短路径的点集合。
  2. 每次从集合 T T T中选出一个与集合 S S S距离最短的点 v v v,将点 v v v加入集合 S S S。通过点 v v v对集合 T T T中的点进行松弛,即更新 T T T中点的最短距离。
  3. 不断重复此步骤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 n1次,每次从集合 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) (n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)

下面对于上述四种方式,分别计算其时间复杂度。

  1. 时 间 复 杂 度 = ( 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} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(n+1+k)=n(n+k)=n2+m=n2
  2. 时 间 复 杂 度 = ( 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} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(1+logn+klog(n))=n(1+k)logn=(n+m)logn
  3. 时 间 复 杂 度 = ( 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} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(logn+logn+klog(n))=n(2+k)logn=(2n+m)logn=(n+m)logn
  4. 时 间 复 杂 度 = ( 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} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(logn+logn+k1)=n(2logn+k)=2nlogn+m=nlogn+m

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/25112.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信