lggp   2년 전

퀵소트를 사용했는데도 시간초과를 당했는데 이유를 알 수 있을까요?

djm03178   2년 전

퀵소트가 느리기 때문입니다. 버블 정렬과 같은 O(n^2)이므로 더 빠른 O(nlogn)의 정렬을 써야 합니다.

lggp   2년 전

퀵 정렬도 O(nlogn) 형태 아닌가요? 그리고 퀵소트가 정렬의 꽃인 줄로 알고 있었는데
그러면 효율성만으로만 따지자면 퀵정렬보다 병합정렬이 좋은 건가요?

circlezer0   2년 전

퀵소트의 pivot을 위와 같이 start로만 잡게 되면, 초기 배열이 오름차순이거나 내림차순인 경우  5,4,3,2,1 -> 4,3,2,1 -> 3,2,1 -> 2,1 -> 1과 같이 정렬을 하기 때문에 O(n^2)입니다.

pivot을 start,end의 중간값으로 잡거나 랜덤한 위치로 설정하면 간단하게 해결할 수 있지만 무조건 O(nlogn)을 보장하지는 않습니다.

더 자세한 내용은 구글에 퀵소트 pivot으로 검색하시면 될 것 같습니다!

circlezer0   2년 전

http://boj.kr/8ea24d77b0c848ba...

http://boj.kr/2a03cb2f59544b8c...

이 문제에서는 중간값으로 잡으면 시간초과가 걸려서 무조건 랜덤피봇으로 설정해야 하는것 같습니다.

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