[일반] 다익스트라 시간복잡도 이해한거 봐주면 안됨?

[익명(223.39)]

인터넷 서치랑 나랑 좀 달라서

노말이 v^2인 이유는 v개의 노드에 대해 (e(인접한 엣지탐색과 최소값 갱신)+v(방문하지 않은 노드중 최소찾기))*v 이어서 이고
여기서 좀 오류가 잇는데
우선순위 큐가 vlogv라고 하는데 (e(인접한 엣지)+logv(최고))*v 이면 v(e+logv)아닌가??

인접한 엣지는 무시하는거야??

내 가정자체가 틀렷든 뭐가 틀렷든 고수님들 알려주시면 ㄱㅅ

[익명(172.226)]

e. log v임

[익명(223.39)]

다 다른듯

[익명(223.39)]

정점 하나가 가진 간선이 E개가 아니잖 가장 가까운 정점을 뽑는 행위가 VlogV 그리고 간선을 가지도 완화하는 행위가 최대 간선 개수만큼 일어나니 ElogV 그래서 (V+E)logV

[익명(223.39)]

간선을 가지도 > 가지고

[익명(223.39)]

1번 노드가 간선 3개 2번이 2개 3번이 4개 가지고 있으면 1,2,3번 노드 순서대로 뽑았다 칠 때 (1 * 3)번 완화 + (1 * 2)번 완화 + (1 * 4)번 완화지 3 * 9번 완화하는게 아니란 뜻

[익명(119.206)]

그러면 가장 가까운 정점용 큐와 간선용 큐가 두개있다고 생각하면 됨??

[익명(119.206)]

나 글쓴이인데 ElogE ~= ElogV 가 되는건 이해함 근데 (V+E)logV는 잘 모르겟네