추가 설명 — quickselect는 왜 평균 O(n)인가

선택 문제 본문은 quickselect를 소개하면서 “대부분 $O(n)$“이라는 말로 평균을 넘어갔다. 최선·최악은 간단히 보였지만, 평균이 정말 $O(n)$인지는 기댓값 점화식을 세우고 직접 풀어야 확인할 수 있다. 이 글이 그 빈칸을 채운다.

---

한쪽만 재귀한다는 차이

quick sort 평균 분석부터 떠올려 보자. pivot의 등수를 $k$라 하면, quick sort는 왼쪽 $k-1$개와 오른쪽 $n-k$개 양쪽 모두를 재귀해야 한다. 그래서 점화식에 $E(k-1) + E(n-k)$가 더해진다. 두 비용을 합산하기 때문에 결국 $\Theta(n \log n)$이 나온다.

quickselect는 다르다. 분할 후 $k$번째 원소가 어느 쪽에 있는지 pivot 등수와 비교해 알 수 있으므로, 관계없는 쪽은 버리고 한쪽만 재귀한다. 그 비용은 $E(k-1)$ 또는 $E(n-k)$ 둘 중 하나다.

최악의 경우를 상계로 잡으면, 어느 쪽으로 재귀하더라도 비용은 $\max\!\bigl(E(k-1),\,E(n-k)\bigr)$ 이하다. 이것이 quick sort 점화식과 quickselect 점화식의 결정적 차이다.

---

기댓값 점화식

pivot의 등수 $k$가 $1$부터 $n$까지 각각 확률 $\frac{1}{n}$로 나온다고 가정한다. 분할 자체는 배열을 한 번 훑으므로 $n$이다. 재귀 비용의 상계를 $\max$ 항으로 잡으면 점화식이 선다.

$$E(n) \le n + \frac{1}{n}\sum_{i=1}^{n}\max\!\bigl(E(i-1),\,E(n-i)\bigr)$$

이것이 풀어야 할 점화식이다.

---

상계 풀이 — $E(n) \le 4n$

수학적 귀납법으로 $E(n) \le 4n$을 보인다.

기저 사례. $E(0) = 0$이고, $n = 1$이면 비교 없이 바로 반환하므로 $E(1) = 0 \le 4$. 둘 다 성립한다.

귀납 가정. $j < n$인 모든 $j$에 대해 $E(j) \le 4j$라고 가정한다.

귀납 단계. 합 안의 각 항에 가정을 먼저 적용한다. $i-1$과 $n-i$는 둘 다 $n$보다 작으므로 가정을 쓸 수 있다.

$$\max\!\bigl(E(i-1),\,E(n-i)\bigr) \;\le\; \max\!\bigl(4(i-1),\,4(n-i)\bigr) \;=\; 4\max(i-1,\,n-i)$$

이제 $\max$가 $E$ 밖으로 나왔다. 점화식에 넣으면

$$E(n) \le n + \frac{4}{n}\sum_{i=1}^{n}\max(i-1,\,n-i)$$

이고, 남은 일은 정수 합 $\sum_{i=1}^{n}\max(i-1,\,n-i)$의 상한뿐이다.

합을 정확히 세기

$i$가 $1$부터 $n$까지 돌 때 $\max(i-1,\,n-i)$가 어떤 값들을 훑는지 $n = 6$과 $n = 7$로 보자.

$i$	1	2	3	4	5	6	7	합
$n = 6$	5	4	3	3	4	5		24
$n = 7$	6	5	4	3	4	5	6	33

짝수 $n$에서는 모든 값이 정확히 두 번씩 나온다. 홀수 $n$에서는 가운데 값 하나가 한 번만 나온다 ($n=7$의 $3$). “각 항이 두 번씩”이라고 뭉뚱그리면 홀수에서 틀리므로, 두 경우를 나눠 센다. $n = 2m$과 $n = 2m+1$로 두면

$$\sum_{i=1}^{n}\max(i-1,\,n-i) = \begin{cases} 2\displaystyle\sum_{j=m}^{2m-1} j = 3m^2 - m, & n = 2m \\[1.2em] 2\displaystyle\sum_{j=m+1}^{2m} j + m = 3m^2 + 2m, & n = 2m+1 \end{cases}$$

이다. 두 값 모두 $\dfrac{3n^2}{4}$ 이하다. 짝수에서는 $3m^2 - m \le 3m^2 = \frac{3n^2}{4}$이고, 홀수에서는 $\frac{3n^2}{4} = 3m^2 + 3m + \frac{3}{4}$이므로 $3m^2 + 2m$보다 $m + \frac{3}{4}$만큼 크다.

$$\sum_{i=1}^{n}\max(i-1,\,n-i) \;\le\; \frac{3n^2}{4}$$

마무리

이를 대입하면

$$E(n) \le n + \frac{4}{n} \cdot \frac{3n^2}{4} = n + 3n = 4n$$

귀납 가정이 $n$에서도 성립한다. 따라서 모든 $n$에 대해 $E(n) \le 4n = O(n)$이다.

$E$의 단조성은 어디에도 쓰이지 않았고, 홀수 $n$의 중앙항도 정확히 한 번으로 세었다.

---