QuickSort(2)-알고리즘04

Worst Case Partitioning 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라진다. 즉 퀵 정렬에서 pivot을 기준으로 분할을 할 때, pivot이 무엇이냐에 따라 연산횟수가 달라진다. 연산횟수를 최대로 만드는 pivot은 무엇일까? 일단 퀵 정렬의 시간복잡도는 T(n)= T(q) + T(n-q-1) + O(n) 이었다. 여기서 q가 n-1이라면 T(n)= T(n-1) + T(1) + O(n) = T(n-2) + T(1) + O(n-1) + T(1) + O(n) =... 이다. 한마디로 배열을 n-1개짜리와 1개짜리 로 분할을 하는 pivot을 선택하는 것이 퀵정렬에서의 최악의 경우이다. 따라서 T(n)=O(n^2) 인데 이를 증명하자. 재귀트리를 이용..

2023.06.30