doraemon0627   1년 전

왜 시간초과가 나는지 모르겠습니다... pivot을 Median-of-three를 이용해서 설정하려고 하였는데 시간 초과가 뜨네요. 그냥 피봇을 랜덤으로 하는 거는 시간초과가 안뜨고요

mythofys   1년 전

퀵 소트 자체가 O(N^2)이기 때문에 얼마든지 해당 코드가 시간 초과가 나게 하는 데이터를 만들 수 있습니다.

예를 들면 제시해주신 코드의 경우 왼쪽 끝, 중앙, 오른쪽 끝에만 작은 수가 많이 분포하는 데이터가 존재한다면 충분히 시간 초과가 날 수 있어 보입니다.

doraemon0627   1년 전

그러면 피봇을 아에 랜덤으로 뽑는게 정답일까요? 다음에는 그냥 머지 소트 쓰던가 해야겠네요.

mythofys   1년 전

랜덤도 시드를 알 수 있으면 이론상으로는 저격 가능하고 그렇게 되면 O(n²)의 시간복잡도를 가지게 됩니다. 웬만하면 stl에 구현되어 있는 std::sort를 사용하면 좋을 것 같네요.

doraemon0627   1년 전

감사합니다

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