준비물

평균 계산 복잡도를 산출하려면 확률 변수와 기대값에 대해 알아야 한다.

확률 변수

Random Variables

A random variable is a function from the sample space of an experiment to the set of real numbers. That is, a random variable assigns a real number to each possible outcome.

확률 변수는 실험의 표본 공간으로부터 실수의 집합으로의 함수다.
확률 변수(함수)는 가능한 모든 결과에 실수를 할당한다.
확률 변수는 주로 X()로 표기한다.

이름은 확률 변수지만 함수라는 점에 주의하자.

확률 변수의 예제

$X$ 가 동전을 두 번 던진 결과 $t$ 에서 앞면의 수를 할당하는 확률 변수(함수)라 하자.

X(t)는 모두 다음의 값을 갖는다.

$\begin{align} X(HH) & = 2 \\ X(HT) & = X(TH) = 1 \\ X(TT) & = 0 \\ \end{align}$

기대값

Expected Values

The expected value, also called the expectation or mean, of the random variable $X$ on the sample space $S$ is equal to
$E(X) = \sum_{s \in S} p(s) X(s)$ .
The deviation of $X$ at $s ∈ S$ is $X(s) − E(X)$ , the difference between the value of $X$ and the mean of $X$ .

표본 공간 에서의 확률 변수 의 기대값(혹은 평균)
- .
  - $p(s)$ : $s$ 의 확률.
- 즉, 각 경우에 대한 확률 변수와 그 확률을 곱한 값을 모두 더한 것이다.
- 즉, 평균이다.
편차는 이다.
- 즉, $X$ 의 값과 $X$ 의 평균과의 차이이다.

평균 계산 복잡도

다음과 같이 정의하자.

$a_j$ : 가능한 입력. $j = 1, 2, ..., n$
$X(a_j)$ : 입력 $a_j$ 에 대해 알고리즘이 사용하는 연산의 수
$p(a_j)$ : $a_j$ 의 확률

그렇다면 $X$ 의 기대값(평균 계산 복잡도)를 다음과 같이 표현할 수 있다.

$E(X) = \sum_{j=1}^n p(a_j) X(a_j)$

예제: 선형 탐색 알고리즘

다음과 같이 선형 탐색 알고리즘을 심플하게 구현한 함수가 있다.

function linearSearch(x, list) {
  let i = 0;
  for (let i = 0; i < list.length; i++) {
    if (list[i] === x) {
      return i;
    }
  }
  return -1;
}

list의 길이가 $n$ 이라 하자.
가능한 결과는 $-1$ 이 리턴되는 경우까지 합쳐서 모두 $n+1$ 개이다.
$x$ 가 리스트에 있을 확률을 $p$ 라 하자.
$x$ 가 리스트에 없을 확률을 $q = 1 - p$ 라 하자.

비교 연산은 매 루프마다 2번씩 일어난다. i < list.length와 list[i] === x

그러므로 다음과 같이 생각할 수 있다.

x가 0번 인덱스에 있다면 필요한 연산의 수는 $2 \times 1$ .
x가 1번 인덱스에 있다면 필요한 연산의 수는 $2 \times 2$ .
…
x가 $n-1$ 번 인덱스(리스트의 마지막)에 있다면 필요한 연산의 수는 $2 \times n$ .
x가 리스트에 없다면 필요한 연산의 수는 $2 \times (n+1) = 2n + 2$

리스트에 x가 있고, 리스트의 i번째 아이템과 x 가 같을 확률은 $p \times { 1 \over n }$ .

따라서 기대값은 다음과 같이 표현할 수 있다.

$\begin{align} E & = {2p \over n} + {4p \over n} + ... + {2np \over n} + (2n + 2)q \\ & = {2p \over n}(1 + 2 + ... + n) + (2n + 2)q \\ & = {2p \over n} \times {n(n+1) \over 2} + (2n + 2)q \\ & = p(n+1) + (2n + 2)q \\ \end{align}$

만약 리스트에 x가 반드시 포함된다고 하면
- $p = 1, q = 0$ 이므로 평균 계산 복잡도는 $n + 1$ 이 된다.
만약 리스트에 x가 존재하지 않는다고 하면
- $p = 0, q = 1$ 이므로 평균 계산 복잡도는 $2n + 2$ 이 된다.
만약 리스트에 x가 존재할 확률이 라면
- $p = q = {1 \over 2}$ 이므로 평균 계산 복잡도는 ${3n +3 \over 2}$ 이 된다.

예제: 삽입 정렬 알고리즘

다음과 같이 삽입 정렬 알고리즘을 심플하게 구현한 함수가 있다. (코드 출처는 한국어 위키백과)

def insert_sort(x):
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1] = x[j]
            j = j - 1
        x[j+1] = key
    return x

정렬할 $n$ 개의 원소 $a_1, a_2, ..., a_n$ 가 있다고 하자.
개의 원소가 정렬된 상태에서, 를 삽입하는데 필요한 비교 연산의 수를 확률변수 라 하자.
- $X_1$ : $0$ 개의 원소가 정렬된 상태에서, $a_1$ 을 삽입하는 데 필요한 비교 연산의 수.
- $X_2$ : $1$ 개의 원소가 정렬된 상태에서, $a_2$ 을 삽입하는 데 필요한 비교 연산의 수.
- …
- $X_n$ : $n-1$ 개의 원소가 정렬된 상태에서, $a_n$ 을 삽입하는 데 필요한 비교 연산의 수.

그런데 확률변수 $X_i$ 는 $i$ 를 알면 바로 얻어낼 수 있는 값일까?

그렇지 않다.

만약 $2,4,13,14$ 가 정렬되어 있는 상태에서 $25$ 를 삽입하려 한다면 $2, 4, 13, 14$ 과 비교해야 할 것이므로 4 번의 비교가 필요하다.

이 경우 $X_5 = 4$ 이다.

하지만 $2,4,13,14$ 가 정렬되어 있는 상태에서 $1$ 을 삽입하려 한다면 $2$ 하고만 비교하면 되므로 1번의 비교로 충분하다.

이 경우 $X_5 = 1$ 이다.

즉 삽입하려는 원소 $a_5$ 가 이미 정렬된 수열의 어느 자리에 들어가야 하는지에 따라 확률 변수 $X_5$ 의 값이 바뀐다.

  a_1,  a_2,  a_3,  a_4
1     2     3     4     5
번    번     번    번    번
자    자     자    자    자
리    리     리    리    리

그러므로 $X_5$ 의 기대값을 다음과 같이 생각할 수 있다.

$\begin{align} E(X_5) & = \text {1번 자리에 들어갈 확률 $\times$ 1번 자리에 들어갈 경우 비교 연산의 수} \\ & + \text {2번 자리에 들어갈 확률 $\times$ 2번 자리에 들어갈 경우 비교 연산의 수} \\ & + \text {3번 자리에 들어갈 확률 $\times$ 3번 자리에 들어갈 경우 비교 연산의 수} \\ & + \text {4번 자리에 들어갈 확률 $\times$ 4번 자리에 들어갈 경우 비교 연산의 수} \\ & + \text {5번 자리에 들어갈 확률 $\times$ 5번 자리에 들어갈 경우 비교 연산의 수} \\ \end{align}$

이걸 기호를 사용하면 조금 더 단순하게 쓸 수 있다.

$\begin{align} E(X_5) & = p_5(1) \times X_i(1) \\ & + p_5(2) \times X_i(2) \\ & + p_5(3) \times X_i(3) \\ & + p_5(4) \times X_i(4) \\ & + p_5(5) \times X_i(5) \\ \end{align}$

$\sum$ 를 쓰면 한 줄로 표현할 수 있다.

$E(X_5) = \sum_{k=1}^5 p_5(k) \times X_i(k) \\$

그런데 1번 자리에 들어가건 2번 자리에 들어가건 수열이 랜덤하게 분포되어 있다면 확률은 다 똑같다.

따라서 다음과 같이 식을 다시 쓸 수 있다.

$\begin{align} E(X_5) & = \sum_{k=1}^5 { 1 \over 5 } \times X_i(k) \\ & = {1 \over 5} \sum_{k=1}^5 X_i(k) \\ \end{align}$

한편, $X_i(k)$ 는 $k$ 번 자리에 들어갈 경우 비교 연산의 수 이므로, 그냥 $k$ 이다.

그러므로 식을 다음과 같이 정리할 수 있다.

$\begin{align} E(X_5) & = {1 \over 5} \sum_{k=1}^5 k \\ & = {1 \over 5} \times { 5 ( 5 + 1 ) \over 2 } \\ \end{align}$

$X_5$ 인 경우를 해 봤으니 $X_i$ 인 경우에 대해서 일반화를 해보면 다음과 같을 것이다.

$\begin{align} E(X_i) & = {1 \over i} \sum_{k=1}^i k \\ & = {1 \over i} \times { i ( i + 1 ) \over 2 } \\ & = { i + 1 \over 2 } \\ \end{align}$

이제 삽입 정렬의 평균 계산 복잡도를 구할 수 있다.

삽입 정렬은 원소를 하나하나 정렬해가므로, 삽입 정렬 과정 전체에 필요한 비교 연산의 수는 다음과 같을 것이다.

$X = X_1 + X_2 + ... + X_n$

$X_1$ 은 $0$ 일 것이므로 $X_1$ 을 제외하고 다시 써보자.

$X = X_2 + X_3 + ... + X_n$

그렇다면 기대값은 다음과 같을 것이다.

$\begin{align} E(X) & = E(X_2 + X_3 + ... + X_n) \\ & = E(X_2) + E(X_3) + ... + E(X_n) \\ \end{align}$

그런데 $E(X_i) = { i + 1 \over 2 }$ 라는 것을 위에서 이미 밝혔으므로 이를 이용하여 다음과 같이 정리할 수 있다.

$\begin{align} E(X) & = E(X_2) + E(X_3) + ... + E(X_n) \\ & = \sum_{i=2}^n E(X_i) \\ & = \sum_{i=2}^n { i + 1 \over 2 } \\ & = \sum_{i=1}^n { i + 1 \over 2 } - { 1 + 1 \over 2 }\\ & = \sum_{i=1}^n { i + 1 \over 2 } - 1 \\ & = \frac{1}{2} \sum_{i=1}^n ( i + 1 ) - 1 \\ & = \frac{1}{2} \sum_{i=1}^n i + \frac{n}{2} - 1 \\ & = \frac{1}{2} \times \frac{n (n+1)}{2} + \frac{n}{2} - 1 \\ & = \frac{n (n+1)}{4} + \frac{2n}{4} - \frac{4}{4} \\ & = \frac{n^2 + 3n - 4}{4} \\ \end{align}$

즉, 삽입 정렬 알고리즘에서 사용하는 비교 연산의 평균 개수는 $\frac{n^2 + 3n - 4}{4}$ 이므로 $\Theta(n^2)$ 이다.

함께 읽기

[[big-O-notation]]

참고문헌

Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일

평균 계산 복잡도 구하기

Average Case Computational Complexity

준비물