퀵정렬이 합병정렬보다 느리지 않아???

[에이시아(203.90)]

 합병정렬은 최악의 경우도 nlgn인데 퀵정렬은 최악의경우 n^2이고 평균이 nlgn이잖아 합병정렬이 퀵정렬보다 느린 것 같진 않은데 아니야???

[그딴건없구염'ㅡ'(invers83)]

퀵정렬이 왜n^2냐?

[그딴건없구염'ㅡ'(invers83)]

퀵정렬 최악의 경우가 n(n-1)/2 거든?ㅡㅡ

[에이시아(203.90)]

최악의 경우 n^2이라고 책에 나와있어...

[에이시아(203.90)]

그게 n^2이지 시간복잡도가

[에이시아(203.90)]

빅오 n

[에이시아(203.90)]

빅오 n^2아냐

[아놔콘다(anwaconda)]

그딴건없구염.. // 허허허.......

[에이시아(203.90)]

작은 찻수는 버려도상관없잖아

[에이시아(203.90)]

허허허.......

[ㅋㄱ(183.96)]

그건최악이고\'

[[성대아싸](skkuassa)]

뻔한 얘기지만 데이터가 랜덤할때 퀵이나, 머지나 똑같이 O(nlogn) 이지만 머지가 머지과정을 수행하는 오버헤드가 있으니까 느리다 는 얘기졍

[에이시아(203.90)]

아 글쿤요...

[에이시아(203.90)]

답변 감사~

[[성대아싸](skkuassa)]

횽생각도 일리가 있는게 아니 맞는게, 빅오가 최악의 경우를 나타내는 것이고, 데이터가 어떤상황이든 제네럴한 동작을 원할경우는 O(n^2)라고 해야겠죠

[에이시아(203.90)]

글쿤요... 그래서 뇌자알에서도 최악의 경우를 피하는 퀵소트를 짜라는 문제도 있엇죠...