ckddnr0408   4년 전

실행 시간이 900대가 나옵니다. 어떤 부분이 문제길래 시간이 이렇게나 오래 걸리는지 모르겠습니다.

900대는 너무하게 길게 나오는데 도와주세요.

slah007   4년 전

qsort는 최악의 경우 O(N^2)이므로 안정적으로 O(N lg N)에 동작하는 heap sort나 merge sort를 사용하는 것이 좋습니다. 매번 구현하기 귀찮다면 c++의 std::sort()를 사용하면 됩니다.

djm03178   4년 전

qsort 저격이 쉽게 가능한가요? qsort를 썼다고 문제가 된 경우는 보지 못한 것 같습니다. 표준상으로는 qsort의 시간 복잡도가 아예 명시되어있지 않고 gcc 구현체에서도 그렇게 쉽게 저격되도록 만들어지지 않은 것으로 압니다.

이 코드는 그 이전에 decision 함수가 O(N^2)인 것이 문제입니다. 27번째 줄의 조건이 단 한 번도 만족되지 않으면 i는 그냥 1 증가하는 것이 문제입니다. 이 경우 바로 루프를 탈출할 수 있도록 바꿔주면 28ms에 통과합니다.

아마 이 코드는 저격이 가능할 것 같네요.

ckddnr0408   4년 전

i를 이동시켜주니 당연히 n번만 반복할줄 알았습니다. 말씀해 주신 내용 다시 보고 생각해 보니 최악의 경우 n^2이 나오네요. 너무 간과했던것 같습니다.

덕분에 또 하나 배우고 갑니다. 가르침 너무너무 감사합니다!!!

0000000000   4년 전

@slah007 qsort()가 최악의 경우 O(N2)이라고 하셨는데 아마 qsort()가 quicksort를 이용한 함수인 것이라고 생각하신 것 같습니다. qsort() 함수는 이름만 quicksort와 비슷할 뿐 quicksort 기법과는 별로 관계가 없는 함수입니다. 또 quicksort도 pivot값을 랜덤으로 잡으면 O(N2)의 시간이 걸릴 확률은 사실상 불가능에 가깝습니다.

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