Approximate Median , Selection Problem

우선 approxmiate median 에 대해 알아보기 전에, Quick Sort에 대해 간단히 짚어보자. Quick Sort 저번 포스팅에서 Quick Sort의 평균 시간복잡도가 왜 O(nlogn) 인지 증명해보았다. 시간복잡도 Average : O(nlogn) Worst : O(n^2) 피벗이 중간에 위치해 있다 -> Best Case 피벗이 한쪽 방향으로 계속 쏠려있다. -> Worst Case 정말 운이 안 좋게도 재귀적으로 따라 들어갈 때마다 pivot 이 한쪽 끝이라면 시간복잡도가 O(n^2) 이다. Quick Sort를 쓰는 의미가 없음. 시간복잡도 (최악의 경우) T(n) = n + T(n-1) T(n) = O(n^2) 이렇게 pivot의 위치에 따라 성능에 크나큰 차이가 발생한다. 따..

2022.10.14