이해가 잘 안되서 질문드립니다.
보통 다익스트라 알고리즘의 시간복잡도가 V^2, ElogV 이렇게 두 가지가 있는 걸로 알고있습니다.(피보나치 힙 E+VlogV 제외)
V^2 의 경우는 모든 정점에 대해서(V) 최소 거리(배열의 최소값)를 찾는(V)작업을 하기 때문에 V^2 인걸 알겠는데요..(경우에 따라선 기존 거리와 새로운 거리의 비교횟수인 E를 더해주기도 합니다만..)
ElogV의 경우(힙)에는 구글링해서 살펴보면 원래 ElogE인데, 중복간선이 없는 그래프의 경우에는 E는 보통 V^2를 넘지 않으니까 ElogV^2 = 2ElogV = O(ElogV) 가 된다고 설명을 하더군요. 나무위키?랑 다른 블로그를 봐도 이렇게 나와있습니다.
여기서 제가 궁금한게
다익스트라 알고리즘이 distance[V]라는 배열을 계속 업데이트하면서 미니멈을 pop하는 형식이잖아요?
그럼 애초에 힙을 V개만 유지할텐데, 어떻게해서 ElogE라는 식이 나오는지 모르겠습니다. 그냥 바로 ElogV가 나오는거같은데..