18870번 - 좌표 압축
두 코드의 계산복잡도가 비슷하다고 생각하는데 왜 시간에 차이가 있나요??
시간 복잡도 차이가 많이 납니다.
시간 초과난 코드에 11번째 줄에서 list의 index 함수를 이용해 압축된 좌표의 index를 구하고 있으신 것 같은데, 이게 한 번에 O(N)만큼 걸립니다.
반면 dict에서 원소에 접근하는 것은 amortized O(1)만큼 걸리니까, 두 코드는 거의 O(N^2)과 O(N)의 차이라고 생각하시면 될 것 같네요.
아하...! 그렇군요 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
clssl15 2년 전
두 코드의 계산복잡도가 비슷하다고 생각하는데 왜 시간에 차이가 있나요??