무작위 알고리즘

1 개요

randomized algorithm, probabilistic algorithm

무작위 알고리즘, 랜덤 알고리즘, 확률적 알고리즘

• 난수의 통계적 특성을 이용하는 알고리즘
• 논리 중 일부에 무작위성을 도입한 알고리즘
• 난수를 발생시켜 진행과정을 결정하는 알고리듬
• 평균적으로 성능 향상

확률적으로 최악의 경우가 방지됨

• 예: 퀵정렬에서 두 묶음을 나눌 때 랜덤값 기준 사용

2 같이 보기

• 분할 정복 알고리즘
• 알고리즘

4 참고

• https://en.wikipedia.org/wiki/Randomized_algorithm