[자료구조 및 알고리즘] (7) Quick sort (퀵 정렬)의 시간 복잡도 증명 (time complexity of quick sort)

지난 글에서 quick sort라는 sorting algorithm을 소개했었다. https://blog.naver.com/eehero/223602962978 [자료구조 및 알고리즘] (6) Quick sort (퀵 정렬)의 소개 1. Quick sort의 소개 quick sort는 정렬 기법 중 하나이다.

실제로 많이 사용되는데, 특징은 다음과 같다... blog.naver.com 이번 글에서는 quick sort의 평균 시간 복잡도가 왜 O(n log n)인지를 증명하려고 한다. 여기서 평균이란 (best + worst) / 2의 개념이 아니라, 같은 array에 대해서 알고리즘을 여러 번 돌렸을 때 평균적으로 어떤 값이 나오냐는 것이다. 1.

Discrete probability recap 먼저 기초적인 확률 개념에 대해서 알아보자. Omega = sample space.

어떤 experiment에 대해서 나올 수 있는 모든 결과값을 말한다. random variable S =...