글 읽기 - test case 에 대해 질문드립니다.

java로 quick-select algorithm으로 풀었습니다.

제가 알기로 quick-select나 quick-sort 둘 다, 이미 정렬 된 경우 시간복잡도가 O(n^2)으로 알고 있습니다.

그래서 O(n^2)의 케이스를 피하기 위해 array를 shuffle을 하죠.

근데 제가 shuffle을 한 코드보다 shuffle을 하지 않은 코드가 걸린 시간이 더 짧게 나왔습니다.

그럼 test case에 N이 굉장히 큰, 이미 정렬된 경우가 없다는 것 아닌가요?

제 생각에 N이 5 * 10 ^ 6이면, N^2일 때 시간초과가 날 거라고 생각됩니다.

즉, 결론적으로 N이 굉장히 큰, 이미 정렬된 case가 추가되어야 하는게 아닐까요?

명세상으로는 그런 케이스도 있어야 할 것 같지만, 문제의 의도가 단순 퀵 셀렉트라면 문제의 성격 자체를 완전히 바꾸는 변경이 되겠네요.

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

Baekjoon Online Judge