확률적분석 (1) 썸네일형 리스트형 랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms) 요새 알고리즘에 어떻게 확률론이 사용되는지를 공부하고 있습니다. 그러면서 예전에는 잘 몰랐거나 어렴풋이만 알던 내용들을 정확히 바로 잡고 있는데요. 그중에서도 가장 기본적인 내용을 하나 가볍게 짚고 넘어 가고자 합니다. 바로 랜덤 알고리즘(randomized algorithm)과 알고리즘의 확률적 분석(probabilistic analysis of algorithm)인데요. 결론을 미리 말씀 드리자면 둘은 서로 다릅니다. 랜덤 알고리즘은 확률 시행이 알고리즘의 내부에서 이루어지는 것을 지칭합니다. 대신 주어지는 입력에 대해서는 어떠한 가정도 존재하지 않죠. 확률 시행이 알고리즘의 내부에서 진행되니, 알고리즘은 동일한 입력에 대해서도 다른 결과를 출력할 수 있습니다. 이러한 알고리즘의 성능을 분석할 때는 .. 이전 1 다음
