limd123   2년 전

정렬하는데 걸리는 시간 nlog n 이고 답 찾는데 n걸려서 결론적으로 시간복잡도가 nlogn인데 왜 시간초과가 나는지 모르겠습니다.

cakelemon   2년 전

이건 qsort 가 잘못 구현된 것 같습니다.

이 qsort 는 배열의 모든 원소가 같을 때 (ex. {5, 5, 5, 5, 5, 5 ....}) O(n2) 에 작동합니다.

아래 코드를 돌려 보면 start 값이 1씩만 늘어남을 확인할 수 있습니다.

이는 모든 원소가 같으면, right 가 배열의 거의 처음 부분까지 가 버려서 그런 것으로 보입니다.

아래의 

qsort(target, start, right - 1);
qsort(target, right + 1, end);

이것을,

qsort(target, start, right - 1);
qsort(target, left, end);

이런 식으로 고치면 아마 될 것 같네요.

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