Randomized Algorithm

확률적 알고리즘이라고도 부르는 randomized 알고리즘은 난수를 발생시켜 진행과정을 결정하는 알고리즘이다. 알고리즘의 성능을 평균적으로 향상시키기 위해 난수를 사용하므로 알고리즘의 성능은 확률 변수이며, 확률변수의 기댓값이 실제로 원하는 성능이다. 알고리즘 성능의 최악의 경우는 일어날 확률이 극히 작기 때문에 대부분 무시한다. (출처 위키피디아)

Randomized Quick Sort

  • For any deterministic quick sort algorithm, there exist classes of inputs which the algorithm takes O(N^2) time.
  • The average was taken over all possivle inputs
  • All my inputs could be in the class
  • Can you make the situation better?
  • It all depends on the pivot: select random pivot!

퀵소트에서 피봇을 선정하는 방법은 여러 가지가 있는데, 그 중 한 가지 방법이 랜덤으로 피봇을 선택하는 것이다. (이렇게 하면 최소값이나 최대값이 선택되는 확률을 크게 줄일 수 있으나, 랜덤으로 선택하기 위한 난수를 뽑아내는 과정에서 성능 저하가 생기기 때문에 사실 그리 좋은 방법은 아니다. 이 방법보다는 처음 세 개 요소 중에서 중간 값을 피봇으로 지정하는 게 좋음.)

Performance

1

매우 높은 확률로 O(N logN) 시간이 걸리고 아주 낮은 확률로 O(N^2) 시간이 걸린다는 것을 알 수 있다.

The Same Conclusion

  • In averages, the situation is similar
  • But all cases are at an even footing
    • 모든 케이스들이 시작이 똑같음
  • This is mostly better

Las Vegas vs. Monte Carlo

  • Las Vegas
    • always correct, running time probabilistic
    • 답은 항상 정확하지만 걸리는 시간이 오락가락
  • Monte Carlo
    • Probabilistically correct, always the same time
    • 걸리는 시간은 항상 같으나 정답일 때도 있고 아닐 때도 있음
  • Las Vegas -> Monte Carlo
    • Stop running if time exceeds limit and output incorrect answer
    • Las Vegas 알고리즘은 Monte Carlo 알고리즘으로 변환 가능하다. time limit이 지나면 그냥 아무거나 출력하도록 하면 됨.
  • Monte Carlo -> Las Vegas
    • You need verifier (that checks the answer for correctness), does not always exist
    • Repeat until the answer is correct
  • Many other kinds exist
  • Monte Carlo 알고리즘도 Las Vegas 알고리즘으로 변환 가능하긴 하지만, 언제나 가능한 것은 아니다. 맞는 답인지 알 수 없는 경우도 있기 때문이다. verifier가 있는 경우는 변환 가능하다.
  • 인수분해처럼 답을 찾아내는 것은 어렵지만, 결과를 주면 답인지 아닌지 판별하기는 쉬운 문제들도 있음.

Sorted Linked List in an Array (Las Vegas)

  • Find a value X in a linked list
  • Deterministic algorithm takes O(N) time

2

순서대로 따라가면 되니까 O(N) 시간이 걸린다.

Sorted Linked List in an Array (Randomized)

  • Select sqrt(N) random members
  • Find the largest among member that is smaller than X
  • Follow the link from that member

동일한 문제를 randomized algorithm으로 풀어보자.

먼저 배열에서 sqrt(N) 개의 멤버를 무작위로 고른 다음, 선택된 멤버들 중 X보다 작으면서 가장 큰 값을 골라 쭉 따라간다.

이렇게 하면 시간이 얼마나 걸릴까?

Analysis

  • Assume k members are selected
  • Let time be O(k + f(n, k))
    • k: k개를 고른 시간
    • f(n, k): list를 따라가는 시간
  • Calculate f(n, k), probability of distance being d= ((n-d)/n)^k - ((n-d-1)/n)^k
    • d 이상이 될 확률 - d + 1 이상이 될 확률

Thus

정확히 X로 떨어지는 경우는 제외

3

And Then

  • k + f(n, k) = k + n/(k+1)
  • best when k ~= sqrt(n)
    • (k + 1) + n/(k+1) - 1 이므로 곱이 일정함. 산술기하 평균 응용?
    • 그래서 아까 linked list에서 일부러 sqrt(n)개를 뽑았던 것이다.