algorithm - ダイクストラのアルゴリズムは線形時間ですか?

Question

O(|E| + |V| log |V|)

ばかげた質問ですが、ログがある場合、それは線形ですか?

Answer 1

いいえ、O(VlogV) =/= O(V) V に対する VlogV の比率が無限に発散するためです。

Answer 2

「ログがある場合、それは線形か」という質問に対する答えはノーです。線形は通常 O(N) を指します

これが意味することは、それがグラフに依存していることであり、エッジと頂点の両方を考慮に入れることで複雑さをより正確に測定できるということです。より単純な境界はO(V^2)、最悪の場合|E|= O(V^2)suchであるためO(|V^2| + |V| log |V|) = O(V^2)です。最良のケース|E| = 0でO(|V| log |V|)は、実行時間は実際には直線的ではありません。