[解決済み] ダイクストラアルゴリズムの時間複雑性計算の理解

質問

以下の隣接リストを用いて、Dijkstra Algorithmの時間計算をbig-O記法で計算したのですが、うまくいきませんでした。しかし、思ったように計算が進まず、順を追って理解することにしました。

1. 各頂点は(V-1)個の頂点と接続できるため、各頂点に隣接する辺の数はV - 1となる。ここで、Eは各頂点に接続するV-1個の辺を表すとする。
2. Finding & min heapにおける各隣接頂点の重みの更新は、O(log(V)) + O(1) または O(log(V)) .
3. したがって、上記のステップ1とステップ2から、ある頂点に隣接するすべての頂点を更新するための時間複雑度はE*(logV)です。 または E*logV .
4. したがって、すべてのV個の頂点に対する時間の複雑さは、V * (E*logV) 、すなわち O(VElogV) .

しかし、Dijkstra Algorithmの時間複雑度はO(ElogV)です。なぜでしょうか？

どのように解決するのですか？

ダイクストラの最短経路アルゴリズムは O(ElogV) というところにあります。

• V は頂点の数
• E はエッジの総数

解析は正しいが、記号の意味が違う! あなたの言うアルゴリズムは O(VElogV) であり、ここで

• V は頂点の数
• E は一つのノードに接続されるエッジの最大数です。

の名前を変更しましょう。 E を N . つまり、ある分析では O(ElogV) と言い、別の分析では O(VNlogV) . どちらも正しく、実際には E = O(VN) . という違いがあります。 ElogV がよりタイトな推定であることです。