noel7781   4년 전

퀵소트를 써서  문제를 풀려고했는데 시간초과 에러가 뜨네요.
어디를 손봐야 할까요?

chogahui05   4년 전

left를 기준으로 pivot을 잡는 방법을 택하셨는데요~

이런 경우에 시간 초과가 걸리겠죠.

noel7781   4년 전

그럼 소팅방법을 바꿔야되나요? merge sort 같은걸 써야 하나요??

chogahui05   4년 전

그러셔도 되고요. 애초에 Merge는

분할하고 합병하는 과정이 있으니.. 대충 n짜리 data에 대해서

(1) n/2짜리 2개로 나누고

(2) n/2짜리를 정렬하고 T(n/2)

(3) 순서 맞춰주고 = n


이여서 T(n) = 2T(n/2) + n이 되고요.

이걸 좌르륵 풀어주면 T(n) = 2(2*T(n/4) + n/2) + n

= 4*T(n/4) + 2n

= 4*(2T(n/8) + n/4) + 2n

=  8T(n/8) + 3n

...

이렇게 전개가 되기 때문에 O(nlogn)쯤 되는 게 맞고요.


아니면 퀵 sort를 하는데, 중위법으로 pivot을 택하는 방법도 있습니다.

간단하게 설명하면

left, right, mid값들을 가져와서, 그것의 중간값을 pivot으로 취해주겠다는 겁니다.

https://stackoverflow.com/ques...

noel7781   4년 전

감사합니다 다시해볼게요

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