알고리즘의 확률론적 분석
Probabilistic analysis of algorithms |
알고리즘 분석에서 알고리즘의 확률론적 분석은 알고리즘이나 계산 문제의 계산 복잡성을 추정하는 접근법이다.이는 가능한 모든 입력값 집합의 확률적 분포에 대한 가정으로부터 시작된다.이 가정은 효율적인 알고리즘을 설계하거나 알려진 알고리즘의 복잡성을 도출하는 데 사용된다.이 접근방식은 확률론적 알고리즘의 접근방식과 동일하지 않지만, 두 가지를 결합할 수 있다.
비확률론적, 보다 구체적으로 결정론적인 알고리즘의 경우, 가장 일반적인 유형의 복잡성은 평균 사례 복잡성과 거의 항상 복잡성이다.평균 사례 복잡성을 얻기 위해, 입력 분포에 주어진 알고리즘의 예상 시간을 평가하는 반면, 거의 항상 복잡성 추정치에 대해서는 알고리즘이 거의 확실히 보유하고 있는 주어진 복잡성 추정치를 인정하는 것으로 평가된다.
확률론적(임의화된) 알고리즘의 확률론적 분석에서는 입력 분포 외에 임의화된 단계에서 가능한 모든 선택의 분포 또는 평균도 고려한다.
