퀵정렬 시간복잡도

[쫀꼬]

안녕하세요
이번국가직 문제도 그렇고 퀵정렬이 약점이라 공부하던중에 궁금한게 생겼습니다

보통 nlogn, 최악 n^2로 알고있습니다만 각각의 경우에 왜 시간복잡도가 저것인지 잘 모르겠습니다.. ㅎㅎ 부끄럽지만 질문드립니다

퀵정렬은 분할정복을 기반으로 한 정렬기법이며, 초기리스트 A의 길이가 n일때 피벗값 x를 기준으로 정렬한 후, 다시 피벗 x의 양옆 리스트 A1, A2도 퀵정렬해가며 초기리스트 A를 정렬하는 것으로 이해하고 있습니다

A의 길이가 n이므로 절반씩 나눠지면 0.5n, 0.25n... 은 알겠으나 외위서 아는것이지 이해해서 아는것이 아닙니다
최악의 경우는 어떤 리스트에서 피벗값을 뭘로 설정하냐에 따라 n^2가 될 수도, 아닐 수도 있는건가요?

이해하기 쉬운 예시나 문제가 있다면 알려주시길 부탁드리겠습니다
감사합니다

[홍재연]

간단하게 다음처럼 정리하면 됩니다.

1 2 3 4 5 처럼 이미 정렬된 리스트를 정렬할 때 최악이 되고 복잡도는 n^2입니다.

[홍재연]

피벗 선택 등은 무관합니다

[쫀꼬]

제가 시간복잡도 빅오표기법을 겉핥기식으로만 대충외워서 헷갈렸네요 이제 이해했습니다 감사합니다!

[kde0419]

퀵정렬이 최악인 경우가 정렬인 이유가 한번 pivoting을 진행할때 1 : n-1 개로 분할이 되는 정렬된 경우입니다 이경우 점화식으로

T(N) = T(N-1) + n 점화식이 나오고 귀납법으로
T(N-1) = T(N-2) + n-1...

T(N) = n + n-1 + n-2 + ... + 1 = n(n-1)/2
O(N^2)가 나옵니다

평균적인 경우는
T(N) = 2*T(N/2) (절반으로 두개가 나뉘어짐) + n

이고 마스터 정리를 통해 O(NlogN) 가 도출됩니다