clssl15   2년 전

두 코드의 계산복잡도가 비슷하다고 생각하는데 왜 시간에 차이가 있나요??

bnb2011   2년 전

시간 복잡도 차이가 많이 납니다.

시간 초과난 코드에 11번째 줄에서 list의 index 함수를 이용해 압축된 좌표의 index를 구하고 있으신 것 같은데, 이게 한 번에 O(N)만큼 걸립니다.

반면 dict에서 원소에 접근하는 것은 amortized O(1)만큼 걸리니까, 두 코드는 거의 O(N^2)과 O(N)의 차이라고 생각하시면 될 것 같네요.

clssl15   2년 전

아하...! 그렇군요 감사합니다!

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