-
카테고리
-
해결 여부
미해결
bisect와 힙의 속도차이
18.05.15 12:57 작성 조회수 244
0
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 배로
계산된 빅오와 비슷하게 증가하였습니다
답변을 작성해보세요.
답변 0