크루스칼 알고리즘 시간복잡도가 왜 (n+m)logm인지 ㅠㅠ..

[빙빙쥐(119.149)]

n이 정점이고 m이 간선일 때

mlogm이 최소 힙 때문인 건 알겠어..

nlogm이 신장트리 구현하는 것 때문인 건 알것같아

n이 n-1개의 정점을 잇는 거니까 그런 것 같고...

그럼 사이클 계산하는게 logm이라는 건데 왜 그런지 모르겠어

ㅜㅜ..

[programmer(successor)]

log m 이란걸 보면 2진탐색, 혹은 2분법 비용이라고 생각하면 돼

[빙빙쥐(119.149)]

그건 아는데... 왜 사이클 검색하는게 logm인지 이해가 안되

[programmer(successor)]

하나 찾는데 드는 비용 말야 바부.

[programmer(successor)]

니가 1000 페이지 짜리 정렬된 영어사전에서 원하는 단어를 찾을때 절반씩 쪼개서 앞이냐 뒤냐 (2분법) 으로 탐색하면

[programmer(successor)]

최대 몇 번 쪼개겠냐

[programmer(successor)]

500, 250, 125, .... 1 되는 순간 끝날거잖아.

[programmer(successor)]

이걸 거꾸로 보면 1, 2, 4, 8 ... 인 셈이니 1024가 되는 순간 다 끝장본거지.

[programmer(successor)]

2의 n 승이 1024 일때 n 은 10이고

[programmer(successor)]

이걸 log 로 표현하면 log 2 를 밑으로 하는 1024 = 10 이란거잖아.

[빙빙쥐(119.149)]

그러니까 사이클 검색하는게 logm이라는 얘기? 무슨말인지 모르겠어..

[programmer(successor)]

니가 적은게 잘못됐네 m 이 꼭지점이고 n 이 간선이야.

[programmer(successor)]

간선 * log 꼭짓점 이라고

[asdfas(98.212)]

? 시간복잡도 O(m log m) = O(m log n) 인데

[빙빙쥐(119.149)]

무슨말인지 모르겠어 사이클 검색하는데 걸리는 시간이 logm은 맞는거야?

[adfasdf(98.212)]

그래프가 disconnected 되어있다면 할말 없다만...

[programmer(successor)]

사이클 검색이라니 뭔... 꼭짓점 하나 찾는거라니깐

[adfasdf(98.212)]

disjoint set 자료구조에서 union/find 가 O(log n) 임. 소팅 하는게 O(m log m) 이고. 즉, O(m log m + m log n) = O(m log m) = O(m log n)

[adfasdf(98.212)]

꼭지점이 왜 나오는겨 여기서;;

[adfasdf(98.212)]

설마 prim 하고 착각하는거?

[빙빙쥐(119.149)]

도저히 모르겠네..

[programmer(successor)]

지금 크루스칼 이야기 하잖아.

[asdfas(98.212)]

그래 크루스칼이 현재 간선을 현재까지 구한 간선 set에 더하면 싸이클이 존재하는지 체크하는거잖아... 그걸 빠르게 체크하려고 disjoint set 자료구조 쓰는거고...

[programmer(successor)]

그니깐, 그래프 구조를 이야기 할때 간선과 꼭짓점을 이야기하는거고 니 말 맞고 꼭짓점이 왜 나오는지 모르겠어?

[asdfsafdf(98.212)]

꼭지점 찾는거라는게 disjoint set 에서 root node 찾는거라는거면 그쪽 말도 맞음.

[asdfas(98.212)]

어쨌든 여기서 O(m log m) 은 간선 소팅에서 나온거란 말이다.

[programmer(successor)]

그니까, 정렬의 대상은 간선인데, 결국 어느 정점이 어디속했는지를 찾는거란 말이잖아.

[programmer(successor)]

써놓은거 내가 읽어보니 좀 이상하긴 하다 ㅡㅡㅋ