Randomized Algorithm - Randomized QuickSort

Las Vegas

• 답은 항상 나오지만, 시간이 랜덤

---

Monte carlo

• 답이 랜덤이지만, 시간이 항상 일정

 

• Las vegas → Monte carlo
  그냥 시간되면 짜르면된다. 그때까지 답 나왔으면 나온거고, 안나왔으면 안나온거고.
• Monte Carlo → Las vegas
  답 안나왔으면 다시 돌린다. 답 나올때까지..

---

Randomized QuickSort

• Pivot을 매번 랜덤하게 결정하기.
• 기존에는 특정입력에 대하여 항상 최악의 경우 O(n^2) 이지만
  랜덤 quicksort는 모든 입력에 대하여 낮은 확률의 최악의 경우가 발생 가능.
  따라서 특정 입력을 계속 사용해야만 하는 경우에 효과적인 알고리즘.