[중간고사] 2-(4). Divide and Conquer - Uneven Split, Selection Problem

- Uneven Split 단답형, 객관식 문제 출제 예정

- Selection Problem

- Proof 를 전부 알 필요는 없지만... 과제를 관련 문제를 내주셔서... Problem 3 - 10번 문제 + 강노 풀 것!

Uneven Split 

Theorem 1

n
αn	(1 - α) n

 

// 0 < α ≤ 1/2

 

 

// 위의 회색 참고

 

 

Theorem 2

n
αn	(1- α-β)n	βn

 

Selection 문제

문제: k번째를 숫자가 뭐야?

https://bblackscene21.tistory.com/10

[ 알고리즘 공부 ] 선택 문제 알고리즘(Selection) (feat.python 파이썬)

 

 

1. Divide - and - Conquer

Proof idea : Partitioning

• Best Case: 정렬된 배열의 중앙 값
  그러나 우리가 무작위로 중앙 값을 피벗으로 선택할 확률은 1/n으로 매우 낮음.
  
• 그러므로, 위의 그림과 같이 n/4부터 3n/4까지의 범위에 있는 경우도  충분히 좋은 pivot이라고 할 수 있음.

• 위의 그림과 같이 가능한 최악의 충분히 좋은 피벗은 더 큰 절반의 공간 파티션을 3n/4개의 항목으로 남겨둠.
  그렇게 반복적으로 생성된 트리의 높이는 어떻게 될까?

 

2. Randomized