[알고리즘] Lower Bound(방해꾼 논법)

-어떤 (해결 가능한) 문제가 주어져 있다고 하자. 그럼 이 문제를 해결하는 algorithm 의 upper bound 와 lower bound 는 어떻게 정의할 수 있을까?

 

1. 해당 문제를 T 시간 안에 해결하는 algorithm 이 존재 한다.

Ex )

-Size 가 n인 array 에서 selection 을 하는 문제의 upper bound 는 O(n) 이다.

-Size 가 n인 array 에서 selection 을 하는 문제의 upper bound 는 O(n2) 이다.

 ->이 경우 첫번째 upper bound 가 더 우수한 upper bound 가 된다.

 

-Strongly connected component 를 구하는 문제의 upper bound 는 O (n+m) 이다.

-Longest increasing subsequence 문제의 upper bound 는 O(n2) 이다.

 

2.해당 문제를 해결하는 algorithm 의 lower bound 가 T 이다                                          

->(어떤 가정 하에서) 해당 문제를 T 시간보다 빨리 해결할 수 없다.

-이 때 가정은 계산 모델, 추가 사용 공간 등 여러가지 가정이 있을 수 있다.

-Lower bound 는 constant 가 명확하지 않은 경우 보통 Ω notation 을 이용해 표기한다.

Ex )

-Size 가  n 인 Array 에서 maximum element 를 찾는 알고리즘의 lower bound 는 Ω(1) 이다.

-Size 가  n 인 Array 에서 maximum element 를 찾는 알고리즘의 lower bound 는 Ω(n) 이다.

-> 이 경우 두번째 lower bound 가 더 우수한 lower bound 가 된다

 

 

-어떤 문제를 해결하는 algorithm 의 upper bound 와 lower bound 가 일치 한다면, 해당 upper bound 를 가진 algorithm 은 optimal algorithm (최상의 알고리즘) 이 된다.

 

어떤 문제를 T 시간 안에 해결하는 optimal algorithm 의 존재를 증명하는 방법.

1. T 시간 안에 문제를 해결하는 algorithm 디자인 (upper bound part).

2. Algorithm 의 lower bound 가 T임을 증명 (lower bound part).

-> 대부분의 문제들의 경우 두 part 의 난이도 차이가 매우 크다.

 

이번에는 그중에서도 Lover Bound를 증명할 수 있는 방법중 방해꾼 논법에 대한 단순하면서도 강력한 밥법에 대해 알아볼 것이다.

 

Adversary argument

-Solver (해결하는 사람) 와 Adversary (상대방, 적) 간의 일종의 game.

-Adversary 는 input 을 가지고 있고, solver 는 input 이 뭔지 확인할 수는 없지만 adversary 에게 질문은 할 수 있다. 

-Adversary 는 solver 의 질문에 대해 대답 (본 슬라이드에서는 YES / NO 로 제한) 을 해야 하며 solver 가 최대한 늦게 문제를 해결하도록 input 을 계속 바꿀 수 있다.

-단, input 을 바꿀 때 consistently (일관성) 를 유지해야 한다 (대답한 내용에 모순되도록 input 을 바꿔줄 수 없다).

-Algorithm 의 lower bound = solver 에게 필요한 최소한의 질문 횟수.

 

Problem : Array A[1, .., 5] 에서 maximum element 의 위치 찾기.

-Adversary Argument 를 이용하되 다른 방법으로 lower bound 를 증명해보자.

-Adversary 에 의해 A[j] > A[i] 임이 판명난 경우 j 는 i 에 이김 (혹은 i 는 j 에게 짐)이라고 하고, Array position set {1, 2, 3, 4, 5} 을 다음과 같이 세 집합으로 나누자.

 

  W : 한번 이상 이겼으면서 한번도 지지 않은 position 들의 집합.

  L : 한번 이상 진 position 들의 집합.

  N : 한번도 비교하지 않은 position 들의 집합

 

-초기 상태는 W and L = ∅, N = {1, 2, 3, 4, 5} 이다.

-N = ∅ 이고 L 의 size 가 n-1 이면 W에 있는 (유일한) position 이 답이 된다.

-N 의 size 가 1 줄거나, L 의 size 가 1 증가할 때마다 1 credit 을 얻는다 하면, 문제를 해결하기 위해서는 최소 4x2 + 1 = 9 credit 이 필요하다.

-Solver 는 input array 는 모르지만 질문을 할 때마다 W, L, N 을 계속해서 업데이트 할 수 있다.

 

A 의 position 들의 set {1, 2, …, n} 을 다음 4개의 set 으로 나누어 보자.

 

U : 한번도 비교하지 않은 position 들의 집합.

W : 한번도 지지 않은 position 들의 집합.

L : 한번도 이기지 못한 position 들의 집합.

N : 한번 이상 이기고, 한번 이상 진 position 들의 집합.

 

Some observations

-{U, W, L, N} 은 A 의 partition 이다.

-Solver 에게 주어진 초기 상태는 U = {1, 2, …, n} , W, L and N = ∅ 이며, |U| = 0,             |W|=|L| = 1, |N|=n-2 일 때 solver 는 무조건 정답을 찾을 수 있다.

-어떤 position 이 한 set 에서 다른 set 으로 옮겨질 때, 1 credit 을 얻는다고 하자. 이때 어떤 position 이 set N 에 가기 위해서는 반드시 set W 나 L 을 거쳐가야 한다                    

-따라서 solver 가 대답하기 위해서는 적어도 2(n-2) + 2 = 2n-2 credit 이 필요하다!

 

-Solver 의 전략 : 최대한 적은 비교 횟수로 많은 credit 따기                                             

-Solver 는 가능한 한 최대한 많이 U 에 속한 두 position 을 비교해 나간다 (유일하게 한번 비교로 2 credit 을 주는 경우). U에 속한 서로 다른 두 position 의 pair 는 n/2 개 존재하므로,  n/2 번의 비교를 통해 n credit 을 얻을 수 있다.

 

-이제 2n-2 – n = n-2 credit 이 남았는데, 이 경우 U 에 속한 두 position 이 존재하지 않으므로 solver 는 아무리 최적의 비교를 해도 1번 비교에 1 credit 밖에 얻지 못한다.

 

-따라서 나머지 n-2 credit 을 얻기 위해 최소 n-2 번의 비교가 필요하고, 이에 따라 minimum 과 maximum position 을 찾기 위해 최소 n/2+(n-2) = 3n/2 -2 번의 비교가  필요하다.

 

번외 

Non-comparison Sort : Counting Sort

O(n)