글 읽기 - 다익스트라 O(|E|+|V|^2) 시간복잡도 방식 질문

1) 시작 정점을 제외한 모든 정점에 대해 == (V-1)

2) - 1. 모든 정점에 대해 시작 정점과 연결된 가장 가까운 정점을 찾아 선택하고 == V

2) - 2. 모든 간선에 대해 선택된 정점과 연결된 간선을 찾아 선택된 정점에 대한 최단 경로 갱신 == E

이니까 (V-1)( V + E ) = (V-1) * V + (V -1) * E 라고밖에 이해가 안되는데

어떻게 E + V^2이 나오는지 모르겠습니다

그리고 이 시간 복잡도가 간략하게

1) * 2)-1 을 하기 때문에 O(|V|^2)이라고 자주 설명되는데

0<=E<=V(V-1)/2 인데

왜 2) -1 > 2) - 2으로 당연하게 계산되는건가요?

모든 간선을 보는 것은 각 정점에 대해 개별적으로 수행하는 것이 아닙니다. 그 정점과 연결된 간선들만 봐야 합니다. 각 정점에 연결된 간선은 O(V)개 뿐이므로 최악의 경우에도 E = O(V^2)이 됩니다.

그렇다면 제가 이해한 식이 (V-1)(V+|V|)이 되는건데 이게 어떻게 |E|+|V|^2에 대응되는건지 알려주실수 있나요 ㅠ

E<= (V-1)*V/2 라서 (V-1) * V 가 E에 대응되는게 맞나요?

(V-1)(V+|V|)의 최고차항은 V^2이니까 이 부분이 V^2이고, 알고리즘이 도는 데 전체에 있어서 모든 간선을 한 번씩 보게 되므로 E입니다.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge