p_ce1052   3년 전

small to large 테크닉으로도 풀릴거같아서 짜봤는데 40퍼쯤에서 시간초과가 나네요 small to large로 못푸는 문제인가요? 그냥 머지소트트리 + euler walk 를 써야하나요? 

slah007   3년 전

small to large를 쓰려면 작은 집합을 A, 큰 집합을 B라 할 때 A와 B를 합칠 때 O(|A|)만큼의 연산만 이루어져야 합니다. 그래야 마지막에 N개로 합쳐질 때 O(N log N)번만 이동함이 보장됩니다.

지금은 두 vector를 합칠 때 아무리 못해도 O(|A|+|B|)가 들어서 총 O(N^2)입니다. 위의 코드처럼 합칠 때마다 sort() 해버리면 더욱 느리고요.

만약 child node에 있는 정렬된 벡터 K개를 parent로 한꺼번에 빠르게 합칠 방법이 있으면 가능할수도 있습니다.

p_ce1052   3년 전

위의 코드에서 작은 집합에서 큰 집합으로 합치고 있는데 왜 시간복잡도가 o(|a|+|b|)라고 하시는지는 잘 이해가 안되네요

slah007   3년 전

위의 코드는 합친 뒤 정렬을 하니 O(A + (A+B)log(A+B)) 입니다.

이를 좀 더 효율적으로 수정하면 merge sort할 때 정렬된 두 배열 합치는 방식으로 바꾸는 정도인데 이게 O(A+B)입니다.

p_ce1052   3년 전

만약 정렬을 하지 않는다고 하면 o(nlogn)시간이 걸리는 코드인건 맞나요? 정렬때문에 시간초과가 나는게 맞는거같습니다

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