jaeung95   4년 전

11931번 algorithm에 있는 sort 써도 되지만..

quick 정렬로 한번 구현해봤습니다.

sort함수가 quick 정렬이 이용되는거로 알고 있는데

제가 짠 코드는 어디서 시간을 많이잡아먹나 본지 시간초과가 뜹니다.

그 원인이 무엇인지 도통 모르겠습니다. 아시는분 계시나요? 감사합니다

gallopsys   4년 전

한 번 테스트케이스로 1부터 1000000까지 오름차순 정렬된 데이터를 한 번 넣어보세요. 왜 시간초과로 터지는지 바로 아실 수 있습니다.


Quicksort는 평균적으로 O(n logn)의 시간복잡도를 가지지만, Quicksort 함수를 Pivot을 왼쪽/오른쪽부터 탐색하도록 설계하셨으니 완벽히 오름차순/내림차순으로 정렬된 데이터를 넣으면 피벗은 맞는 조건을 찾을동안 배열 n바퀴를 한 번 더 돌게 됩니다. 그래서 최악의 경우 O(n2)의 시간복잡도를 가질 수도 있는 것입니다.


Quicksort로 해결하고 싶으시면, 배열의 중간부분을 피벗으로 잡으시거나 듀얼 피벗 방식을 한 번 이용해보시는 걸 추천드립니다.

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