무작위 알고리즘(Randomize Algorithm)

무작위 알고리즘(Randomize Algorithm)이란?

 무작위 알고리즘은 난수를 발생시켜 진행과정을 결정하는 알고리즘이다.
난수를 발생시키는 과정은 흔히 '동전을 던진다'거 표현하며, 실제로는 의사 난수 생성기를 사용한다.
알고리즘의 성능을 평균적으로 향상시키기 위해 난수를 사용한다.
난수를 사용하기 때문에 알고리즘의 성능은 확률변수이며, 확률변수의 기댓값이 실제로 원하는 성능이다.
알고리즘 성능의 최악의 경우는 일어날 확률이 극히 작기 때문에 대부분 무시한다.

 평균의 경우(Average Case)의 확률론적 분석을 위해 주어진 입력을 Randomizing 한다.
알고리즘의 Best/Worst Case를 회피하고 일반적 경우에 대한 확률을 구하기 위해 사용된다.

알고리즘의 종류

• Premute-By-Sorting : 원소마다 임의의 우선순위를 부여하고 정렬 시행
• Randomize-In-Place : index값인 i와 i~n 사이의 임의의 위치 교환

Quicksort의 예

Pivot들이 역순으로 정렬된 경우 SubArray 가 불균형적으로 구성되므로 최악의 경우(Worst Case)가 되므로 Insertion Sort(삽입 정렬)와 같은 복잡도를 가짐. 
이를 회피하기 위해 Pivot의 위치를 Randmize 하여 섞음으로써 최악의 경우(Worst Case)를 회피하고 평균의 경우(Average Case)에 가깝게 함

참고 사이트

- 확률적 알고리즘 : https://ko.wikipedia.org/wiki/%ED%99%95%EB%A5%A0%EC%A0%81_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

확률적 알고리즘 - 위키백과, 우리 모두의 백과사전

- 랜덤 알고리즘과 알고리즘의 확률적 분석 : https://gazelle-and-cs.tistory.com/75

랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms)

- Randomized algorithms : http://egloos.zum.com/itfs/v/9697030

5.3 Randomized algorithms