4. Probabilistic Analysis and Randomized Algorithm

알고리즘의 성능을 평가할 때, Time complexity를 분석하며, 이 값은 Input 데이터에 의해 바뀔 수 있다고 학습했습니다. Upper bound, Lower bound, Tight bound를 구하는 노력이 알고리즘의 Best case, Worst case, Average case와 관련이 있게 되는 이유이고요.

 

우리가 알고리즘을 평가할 때, Best case는 별로 관심이 없습니다. 실질적으로 사용하기 위해서는 Worst case와 Average case가 중요하기 때문입니다.

 

Worst case에 대한 시간 복잡도는 비교적 쉽게 구할 수 있습니다. 알고리즘의 수도 코드를 보면서, 최악의 경우를 가정하고 instruction을 따라가면 되기 때문입니다. 반면 Average case는 가능한 모든 Input에 대한 알고리즘의 Time complexity를 구하고 평균을 내야 합니다. 현실적으로 모든 경우의 수를 고려해 계산하는 것은 어렵기 때문에, 다른 방법을 사용하게 되고 그 방법이 바로 Probabilistic Analysis입니다.

 

Probabilistic Analysis

이를 수행하기 위해서는 중요한 가정이 있습니다. 바로 Input 데이터가 uniform distribution을 따른 다는 것입니다. 이 가정 덕분에 우리는 probabilistic analysis를 할 수 있습니다. 다음의 문제를 가정해 봅시다.

 

The Hiring Problem

새로운 직원을 한 명 뽑을 건데, 얼마만큼의 비용이 드는지 계산하는 문제입니다. 인터뷰하는 비용을 $c_i$, 고용하는 비용을 $c_h$라고 합시다. 그리고 알고리즘은 다음과 같습니다.

Hiring an employee algorithm

Best-case Analysis 

첫 지원자가 바로 고용되는 경우입니다. $c_i+c_h$의 비용이 듭니다.

 

Worst-case Analysis

마지막 지원자가 고용되는 경우입니다. $c_i×n+c_h$의 비용이 듭니다.

 

Average-case Analysis

첫번째 지원자부터, 마지막 지원자까지 각 경우에 고용되는 경우, 비용을 계산합니다.

 

$c_i×1+c_h$

$c_i×2+c_h$

$c_i×3+c_h$

...

$c_i×n+c_h$

 

합쳐서 $c_i×(1+2+...+n)+c_h×n$이 되고 평균을 내면, ${n-1 \over 2}c_i+c_h$의 비용이 드는 것을 알 수 있습니다.

 

Randomized Algorithm

Input이 uniform distribution이라는 가정이 없으면 어떻게 계산할까요? 가능한 모든 경우에 대해 확률을 구해 개별적으로 Time complexity를 구해야하는 번거로움이 생깁니다. 현실적으로 어려울 수 있는 문제이고, 이에 따라 input을 uniform하게 바꾸어주는 알고리즘을 선택해 사용하기도 합니다.

 

대표적으로 랜덤 알고리즘들이 있습니다. 정말로 랜덤성을 원해서 랜덤 알고리즘을 사용하기도 하지만, 알고리즘에 대한 Input의 distribution이 uniform하지 않을 때, 랜덤 알고리즘을 사용함으로써, input이 uniform distribution을 가지도록 만들 수 있습니다.

 

살펴보던 Hiring 문제도 input을 random하게 섞어주면, Input이 uniform distribution을 가진다고 말할 수 있게 됩니다.

Radomized hire algorithm

 

Permute-by-sorting algorithm

Random하게 정렬하는 알고리즘

이 알고리즘의 실행결과물의 확률은 P = ${1 \over n!}$이 됩니다. 다음의 그림처럼 permutation이 생성되기 때문입니다.

 

해서 Complexity는 다음과 같습니다.

 

$T(n) = T(random) + T(sorting)=n+T(nlogn)=O(nlogn)$

$S(A) = O(n)$

 

Randomize in-place algorithm

In-place swap을 적용한 랜덤 정렬 알고리즘

In-place swap을 이용하게 되면, $T(n)=O(n)$에 $S(A)=O(1)$이라는 더 좋은 성능을 얻을 수 있습니다. 다만 original data를 잃게되는 단점이 있습니다.

 

Online problem

Best person을 n명 보고 뽑는 것은 어려운 일입니다. 또한, n명을 모두 보지 않고 best를 뽑는 확률이 높을 수 있습니다.

 

• $s$ : hire the best person
• $s_i$ : hire the $i^{th}$ candidate when $i^{th}$ is the best

 

$Pr(s) = {1\over n}$이 기본적인 Pr이 되고 우리는 이거보다 높이고 싶은게 문제입니다. 그러기 위해서 [1...k] 까지의 점수 중 best를 찾고 [k+1...n] 중에서 best를 넘는 지원자를 찾을 것입니다.

 

그러면, $s_i$에 대한 $Pr(s)$는 다음과 같이 구할 수 있습니다.

 

$Pr(s) = \sum_{i=1}^{n} Pr(s_i) = \sum_{i=k+1}^{n} Pr(s_i)$

 

그리고 다음의 식에 의해 $Pr(s)$를 구할 수 있습니다.

 

대입해서 정리해보면, $k={n \over e}$가 되고 이때 $Pr(s)≥{1 \over e}≒0.37$가 됩니다. 이를 통해 n이 대충 3 이상이면, online algorithm을 사용하는 것이 확률적으로 더 이득임을 알 수 있습니다.