rimm39   2년 전

qsort로 배열을 정렬하고 이진 탐색으로 찾았습니다

stdlib의 qsort를 사용하면 답이 맞는걸로 봐서 qsort 구현이 잘못된 것 같은데

어떤 부분 때문에 시간이 초과되는지 궁금합니다

djs100201   2년 전

qsort는 최악의 경우에 o(n^2)입니다.
직접 구현할 경우에 pivot을 random으로 섞어주는등 몇가지 휴리스틱한 최적화가 필요합니다.

djm03178   2년 전

C 라이브러리의 qsort는 퀵소트로 구현해야 한다는 명세 자체가 없습니다. 이름만 퀵소트에서 따왔을 뿐 내부적으로는 퀵소트가 전혀 아닌 것을 사용하고 있을 수도 있고, 퀵소트라고 하더라도 단순히 정렬된 상태로만 입력이 주어져도 O(n^2)의 시간이 걸리는 기본형을 쓰지는 않을 것입니다. 직접 퀵소트를 구현하면 여러 최적화 기법을 쓰지 않는 한 단순한 데이터에 대해서도 O(n^2)이 될 수 있으므로 직접 정렬을 구현할 거라면 병합 정렬같이 O(nlogn)이 보장되는 것을 쓰시기를 권장합니다.

rimm39   2년 전

감사합니다

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