Algorithm _#4 선택 알고리즘

선택문제

• 입력: n개의 값과 k(1<=k<=n) 값
• 출력: k번쨰로 작은 입력 값
• 목표: 비교횟수 최소화

예시

k = n (최댓값 찾기)

-> n - 1 번 비교 필요, 충분

​ (상한 = 하한)

• 상한(upperbound): (n - 1)번의 비교만으로도 찾기 가능

• 하한(lower bound): 최소 (n - 1)번의 비교해야함

상한 = 하한일때 문제 해결됨

k = 1, n ( 최솟값, 최댓값 찾기)

• 상한

• 하한

• 상한: 2n - 3

  -> 최댓값: n - 1

  -> 최솟값: n - 2

• 하한: 3n/2 - 2

  -> 최댓값: n - 1

  -> 최솟값: n/2 - 1

  (최댓값을 찾을 때 처음에 떨어진 것들 중에서 찾기)

k = 1, 2 (최솟값, 두번째로 작은 값)

• 상한: 2n - 3

  -> 최솟값: n - 1

  -> 두번째로 작은 값: n - 2

• 하한: n - [log2 n] - 2

  -> 최솟값: n - 1

  -> 두번째로 작은 값: log2 n -1 (= round 수 - 1)

  ( 최솟값과 만나서 진 값들 중에서 찾기)

선택 문제 알고리즘

Quick Select

• L: n개의 숫자가 들어있는 리스트

1. p(= pivot) 고르기

2. A = {p보다 작은 값}

B = {p보다 큰 값}

M = {p와 같은 값}

=> (n - 1)번 비교

1. if |A| > k :
   	# A에서 k번째 작은 값 => 재귀적으로 찾기!
   	 (= M과 B에는 없음!)
      
   elif |A| + |M| < k :
   	# B에서 (k - |A| - |M|)번째로 작은 값 찾기
      
   else:
   	# M
   	return P
   

def quick-select(L, k):
	# L: List, k: 정수 값
	p = L[0]
	A, B, M = [],[],[]
	for x in L:
		if p > x: A.append(x)
		elif p < x: B.append(x)
		else: M.append(x)
		
		if len(A) > k :
        	return quick-select(A, k)
		elif len(A) + len(M) < k: 
			return quick-select(B,k-|A|-|M|)
		else: return p

예시

• 문제:

  • L: 6 5 1 7 9 3 8 10 2

  • n = 9, k = 8

  • p = L[0]

• 풀이

  A: 5 1 3 2

  M: 6

  B: 7 9 8 10

  => B에서 3번째로 작은수

  => quick-select(B, 3)

• 시간복잡도:

  • Worst case:

    => P의 한쪽으로만 몰린 경우

    T(n) = T(n - 1) + n

    ​ =…

    ​ =1+2+….+n

    ​ = n(n+1)/2

    ​ => O(n^2)

  • Best case:

    => P를 기준으로 계속 반으로 나눠지는 경우

    T(n) = T(n/2) + n

    ​ (n = 2^k 라 가정)

    ​ = (T(n/2^2) + n/2) + n

    ​ = …

    ​ = T(n/2^k) + n/2^(k-1 )+ … + n/2 + n

    ​ = n(1+1/2 + ... + 1/2^k)

    ​ <= 2n

    ​ => O(n)

=> O(n) (Average case)

• p의 좋은 조건:

  A

  <= n/c

  B

  <= n/c

  => O(nlogn)

  

MoM(Median of Medians)

-> quick-select에서 p를 정할 떄 조건에 맞게 정하는 것

MoM(L, k):

1. 5개씩 group

   (group 수: n/5)

   -> 0번 비교

2. 각 그룹의 중간값(median)

   -> 각 묶음, 즉 5개 중간값의 중간값찾기

   -> n/5 * 갯수

3. **m * = MoM(medians,

   medians

   /2)**

   -> 새로운 중간값 m* 자리

   -> T(n/5)

4. m*를 pivot으로

   => m*들을 기준으로 그룹들을 재정렬 & 그룹 내 재정렬

   -> n번 비교

5. 재귀 호출 or return m*

   ***-> T(

   A

   ) or T(

   B

   )***

시간복잡도:

T(n) = T(n/c) + T(n/5) + 11n/5

• x < m*

• w > m*

• y,z: 모름

A = X + {Y와 Z의 값들중 m*보다 작은것}

B= X+ {Y와 Z의 값들중 m*보다 큰 것}

**=>

A

> k 이면 k번째로 작은 값이 A에 있으니 A에 재귀호출**

**=>

A

+

M

< k 이면 k번째로 작은 값이 B에 있으니 B 재귀호출**

• **n/4<=

  A

  <= 3n/4**

  (x) (x,y,z)

• **n/4<=

  B

  <= 3n/4**

  (x) (x,y,z)

​ => c = 4/3

**( T(

A

), T(

B

) < T(c/n) )**

따라서 T(n) = T(3n/4) + T(n/5) + 11n/5

​ 재귀호출 mom 찾기

귀납법

귀납법

1. base case

   (n = 1 일때 성립함을 증명)

2. < n 일때 등식이 성립한다 가정

3. = n일때 증명!

• T(n) = T(3n/4) + T(n/5) + 11n/5
• 가정: T(n) <= 44n

1. Base case

   n = 1 -> T(1) = 1 <= 44

   => 성립!

2. <n일떄 성립 가정

   T(n) <= 44n 이라 가정

3. T(n)= T(3n/4) + T(n/5) + 11n/5 증명

   ​ <= 44 * 3n/4 + 44 * n/5 + 11n/5

   ​ = 44n

   ​ => T(n) <= 44n

   따라서 T(n) <= 44n이므로 O(n)

   ​

   ​

   44n이 나온 과정

   T(n) <= cn

   T(n) <= 3cn/4 + cn/5 + 11n/5 <= cn

   ​ 44<= c