[질문] Prim Kruskal 질문

[부싼사나이다임..(freedomwind7)]

일반적인 경우는 크루스칼의 시간복잡도가 nlog n  프림은
N^2 간선이 많은경우는 프림은 그대로고 크루스칼은 n^2logn 까지 올라가는데 정렬하는데 시간이 걸리는 건가요?? 아니면 순환노드인지 판별하는데 시간이 걸리는 건가요??

[0xrgb(0xrgb)]

크루스칼 애초에 E log V임

[0xrgb(0xrgb)]

그리고 프림도 구현에 따라서 시간 복잡도 달라지는데, O(V^2), O(ElogV), O(E + VlogV) 셋 다 가능함

[부싼사나이다임마(freedomwind7)]

갤주님 크루스칼이 Elog V 인 이유가 먼가요 정렬하는데 드는비용은 ElogE 일텐데 sort 정렬이 되잇다는 가정하에 복잡도 인가요??

[부싼사나이다임마(freedomwind7)]

아! 깨달앗습니다

[0xrgb(0xrgb)]

E log E인데 잘 생각해보면 E log V^2 = 2 E log V 라서 그럼. 왜 V로 표기하는게 관행인지는 나도 모름

[부싼사나이다임마(freedomwind7)]

감사합니당

[0xrgb(0xrgb)]

순환노드 판별은 Union Find 쓰는데 연산 비용 비싸지 않음

[부싼사나이다임마(freedomwind7)]

V가 노드 개수 E가 간선의 개수 군요 감사합니다!