[Algorithm] 幅優先検索時間の複雑さの分析


Answers

O(1)操作をL回実行すると、 O(1) O(L)複雑さが生じます。 したがって、キューからの頂点の削除と追加はO(1)ですが、 V頂点に対して行うとO(V)複雑さが生じます。 したがって、 O(V) + O(E) = O(V+E)

Question

頂点の各隣接する辺を越える時間の複雑さは、例えば、 O(N)であり、Nは隣接する辺の数である。 したがって、V個の頂点の場合、時間の複雑さはO(V*N) = O(E)になります.Eはグラフ内のエッジの総数です。 キューからの頂点の削除と追加はO(1)であるため、 O(V+E)としてBFSの全体の時間複雑度に追加されるのはなぜですか。




I understood the part V+E in the complexity.
But I have 2 questions
1). V * Eaj should give 2E?
(as it is the total no of edges accessed, and each edge is checked twice, by each of it ends)

2) Also the complexity is V + E
but in worst case we take E = V*(V-1)/2
So V isn't required here as we could say we  E = V²...
Can't we say complexity O(E) only?