Inflearn Community Q&A

bisect가 힙보다 정렬속도가 빠르다고 하셨는데

제가 알기로는 힙이 bisect보다 빠르다고 알고있습니다

제가 힙과 bisect의 빅오를 계산해 보면

힙의 경우는 최악일때 nlogn (log의 밑은 2)

bisect의 경우 최악일때는 n^2

이 나오는것 아닌가요?

또한 제가 코드를 짜서 실험해본 결과

데이터가 10만개의 경우에 정렬시간은 각각

힙은 0.33801937103271484초

bisect는 1.6080927658081055 초

데이터가 100만개의 경우에

힙은 3.945225715637207초

bisect는 136.1947898864746초가 나왔습니다

데이터가 10배 증가하였을 경우에

힙은 약 11.6715배

bisect는 약 84.69336 배로

계산된 빅오와 비슷하게 증가하였습니다