Introduction to Algorithms 3판 연습문제 pg.180
7.2-5
퀵 정렬이 모든 단계에서 1-a 대 a의 비율로 분할한다고 하자. 여기서 0 < a <= 1/2 이고, a는 상수이다. 재귀 트리에서 리프의 최소 깊이는 근사값으로 -log(n)/log(a) 이고, 최대 깊이는 근사값으로 -log(n)/log(1-a)임을 보여라. (반올림은 고려하지 않아도 된다.)
최소 깊이는 반복적으로 작은 하위 문제들을 처리하는 것을 나타낸다.
총 n개의 요소들을 1:9의 비율로 쪼갠다고했을 때, 1/10 으로 쪼갠 부분쪽에서 재귀 트리의 높이의 k 라고 하자.
(n -> 1/10n -> 1/100n -> ... 1까지 도달했을 때 이 가지 부분의 높이를 k라 하는 것)
트리의 단계는 a에 비례하여 k단계만큼 내려간 후 1에 도달한다고 했을때,
a^k*n = 1 로 이를 표현할 수 있다. 따라서, k = loga(1/n) = -log(n)/log(a)이다.
최대 깊이는 항상 더 큰 하위 문제들을 처리하는 것이다. 그렇다면 동일한 논리로 -log(n)/log(1-a)를 얻을 수 있다.
7.2-6
0<a<=1/2 인 모든 상수 a와 임의의 입력 배열에 대해 PARTITION 이 1-a 대 a 보다 균등한 분할을 할 확률은 근사값으로 1-2a 임을 증명해라.
'Algorithms' 카테고리의 다른 글
| [Greedy] 미적으로 아름다운 나무 (0) | 2022.10.28 |
|---|---|
| [프로그래머스] 연습문제 - 기능개발 (0) | 2020.11.30 |
| [프로그래머스] 연습문제 - 주식가격 (0) | 2020.11.30 |
| [프로그래머스] 연습문제 - 위장 (0) | 2020.11.30 |