균등하다는 가정
유한한 가능한 입력들이 모두 같은 확률이라면 비용을 합해 입력 수로 나눌 수 있다. 확률이 다르면 각 비용에 해당 확률을 곱해 더한다. 현실의 모든 입력이 자동으로 같은 확률을 갖는 것은 아니다.
탐색 비교 횟수
n개 원소의 선형 탐색에서 목표가 반드시 존재하고 각 위치에 있을 확률이 같다고 하자. 비교 횟수는 1부터 n까지 같은 확률로 나타나 평균은 (n+1)/2다. 목표가 없는 경우도 허용하면 그 확률을 포함해 다시 계산해야 한다.
최악 분석과 비교
평균 비용이 작아도 특정 입력의 비용은 클 수 있다. 평균 분석은 어떤 입력에서든 일정 시간 안에 끝난다는 보장과 다르다. 반대로 최악 분석만으로 자주 나타나는 입력의 실제 경향을 모두 설명할 수는 없다.
분할 상환과의 차이
분할 상환 분석은 연속한 연산들의 총비용을 통해 연산당 비용을 평가하며 입력의 확률 가정이 필수는 아니다. 한편 무작위 알고리즘의 기대 비용은 알고리즘 내부 난수에 대한 평균일 수 있어 입력 분포에 대한 평균과도 구별한다.
관련 문서
최악의 경우 분석 / 기댓값 / 확률분포 / 선형 탐색 / 시간 복잡도 / 분할 상환 분석 / 알고리즘 / 빅오 표기법