Worst cases, Average cases, and Best cases
알고리즘을 분석 할 때 세 가지 경우로 나눌 수 있다. 워스트 케이스, 에버리지 케이스, 베스트 케이스 세 가지가 있다. 선형 탐색(Linear search)을 예로 들어보자.
최악의 경우
최악의 경우는 알고리즘이 실행되는 시간의 상한을 결정한다. 프로그램을 실행 할 때 연산이 수행되는 횟수가 최대가 되는 경우이다. 선형 탐색의 경우 찾으려는 원소가 배열에 존재하지 않거나 배열의 끝에 존재하는 경우이다. 배열에 찾으려는 원소가 존재하지 않으면 배열의 전체 원소와 모두 비교를 한다. 따라서 선형 탐색의 최악의 경우 시간 복잡도는 $\large \theta (n)$ 이다.
평균적인 경우
평균적인 경우를 계산하는 방법은 다음과 같다. 가능한 모든 입력에 대해 실행 시간을 계산한다. 그리고 이 시간을 모두 더하고, 더한 결과를 입력의 수로 나눈다.
선형 탐색의 Average case time complexity를 계산하는 방법은 다음과 같다.
선형 탐색인 경우 모든 경우들이 균등하게 분포한다고 가정하자. (uniformly distributed)
크기 n의 배열에서 원소 x를 찾으려고 할 때, x의 위치는 1 또는 2, 3, ... , n이 될 수 있다.
배열을 따라 각 원소를 x와 비교한다. 만약 배열의 k번 째 원소에 도달 했으면 이미 k번 비교를 한 것이다.
x가 인덱스 1의 위치에 있다면 1번 비교한다.
x가 인덱스 2의 위치에 있다면 2번 비교한다.
...
x가 인덱스 n의 위치에 있다면 n번 비교한다.
평균을 구하기 위해 비교한 수들을 합하면 $\large 1+2+3+\cdots +n=\frac{(n+1)n}{2}$ 이다.
이를 배열의 크기인 n으로 나누면 $\large \frac{n+1}{2}$ 이다.
따라서 선형탐색의 평균 시간 복잡도는 $\large \theta (n)$ 이다.
조금 더 formal하게 증명할 수 있다.
입력이 uniform probability를 가지고 배열 크기는 n이라 하자.
$\large X$를 비교 횟수를 나타내는 랜덤 변수라 하자.
$\large p(X=x)$는 $\large x$번 비교할 때의 확률이다.
확률 분포가 uniform이므로 $\large p(X=x)=\frac{1}{n}$이다.
기댓값을 계산하면 아래와 같다.
$\large E[X] = \sum_{x=1}^{n}{xp(x)} = \sum_{x=1}^{n}{\frac{x}{n}} = \frac{1}{n}+ \frac{2}{n} + \dots +\frac{n}{n} = \frac{n+1}{2}$
최상의 경우
최상의 경우는 프로그램 실행 시간의 하한을 계산한다. 선형 탐색의 경우 베스트 케이스는 찾으려는 x가 제일 처음에 위치하는 경우이다. 최상의 경우 실행되는 연산의 수는 상수이며 입력 크기 n에 영향을 받지 않는다. 따라서 최상의 경우 시간 복잡도는 $\large \theta (1)$이다.
알고리즘의 하한을 보장하는 것은 특별한 정보를 주지 못한다. 하한을 보장해도 최악의 경우 실행 시간이 몇 십년이 걸리면 아무 소용이 없다.
몇몇 알고리즘들은 모든 경우에 점근적으로 같은 성능을 가지는 경우가 많다. 이는 다시 말하면 최악의 경우든 최상의 경우든 성능이 같아진다는 말이다. 예를 들어 합병 정렬은 모든 경우에 $\large \theta (nlogn)$의 성능을 보인다.
선형 탐색 소스 코드
https://www.geeksforgeeks.org/analysis-of-algorithms-set-2-asymptotic-analysis/
댓글