Coding_Algorithm/DS_Algorithm
Probabilistic Analysis
Probabilistic Analysis 0. 개요 기존에는 알고리즘의 시간분석도를 계산할 때 알고리즘에서 실행되는 명령어의 수를 계산하는 방식으로 진행했다. 특히 worst case로 진행해 그러나 많은 알고리즘은 주어지는 입력에 따라 성능이 달라지는 경우가 많다. 이렇게 입력이 확률적으로 주어지는 상황에서, 입력에 대한 worst case로 성능을 보는 것이 아닌, 평균적인 성능으로 알고리즘의 성능을 분석하는 방법을 알고리즘의 확률적 분석이라고 한다. 다만 확률적 분석은 입력의 분포를 알고 있다는 가정 하에 진행된다. 입력의 분포를 모른다면 확률적 분포를 진행할 수 없다. 1. Hiring Problem Hiring Problem은 사람을 채용할 때의 문제를 칭한다. 각각 사람을 면접볼 때 비용이 들..