[알고리즘] 알고리즘 분석 방법

💡 알고리즘의 분석

알고리즘의 성능을 평가하기 위한 분석으로, 크게 수행 시간(시간 복잡도)과 필요한 기억 장치의 양(공간 복잡도)으로 평가되는데, 대부분의 경우에 수행 시간이 더 중요한 의미를 지닌다. 따라서, 해당 글에서는 시간 복잡도 분석을 통해 설계한 알고리즘이 얼마나 효율적으로 문제를 풀어내는가에 대한 지표를 제시하고 판단의 근거를 제시하는 방법을 나열한다.

시간 복잡도 분석이란 입력크기에 따라 단위연산이 몇 번 수행되는지 결정하는 절차이다.

 

 

💡 분석 방법의 종류

1. 일정시간 (모든 경우) 분석 (Every-case analysis)

입력 값에는 종속되지 않으며, 입력 크기에만 종속되어 있는 경우이다. 즉, 입력 값에 상관없이 항상 연산의 실행 횟수가 동일한 경우를 의미하며, 아래에서의 $T(n)$을 구하는 과정이 시간 복잡도 분석이다.

 

예시1 : 합계 알고리즘

(1) 입력크기 : S배열의 원소 개수

(2) 단위연산 : 배열의 원소를 result에 더함

result = 0
S = [1, 2, 3, 4, 5]

for i in S:
   result += i

 

배열의 각 원소의 값(입력 값)과는 무관하게 for문은 반드시 배열의 크기(입력 크기)만큼 실행된다.

따라서, 단위 연산의 총 횟수(시간복잡도)는 $T(n) = n$

 

예시2 : 교환정렬 알고리즘

(1) 입력크기 : 배열의 원소 개수 ($len(S)$)

(2) 단위연산 : $S[j] < S[i]$ 비교 (조건문)

for i in range(len(S)):
    for j in range(i + 1, len(S)):
        if S[j] < S[i]:
            S[i], S[j] = S[j], S[i]

 

입력 값에 상관없이 입력 크기(배열의 크기)만큼 값의 비교가 일어나기 때문에 일정 시간 분석을 실행할 수 있다. 

따라서, 일정 시간 분석 결과 조건문의 총 수행횟수는 

$$T(n) = (n - 1) + (n - 2) + ... + 1 = \frac {(n - 1) n} {2}$$

$i = 0$일 때, 비교횟수는 $n - 1$번

$i = 1$일 때, 비교횟수는 $n - 2$번

$...$

 

2. 최악의 경우 분석 (Worst-case analysis)

입력 값과 입력 크기 모두에 종속되어 있는 경우로, 단위연산이 수행되는 횟수가 최대인 경우를 선택하는 분석방법이다.

 

예시 : 순차검색 알고리즘

(1) 입력크기 : 배열의 원소 개수 ($len(S)$)

(2) 단위연산 : 배열의 각 값과 x(찾고자 하는 값)값의 비교

x = 4
S = [1, 2, 3, 4, 5]
cnt = 0

for i in S:
    if i == x:
        break;
    cnt += 1

 

배열의 크기가 n이라고 할 때, x에 해당하는 값이 배열의 맨 마지막에 위치하거나 x가 배열에 없는 경우  for문이 n만큼 실행된다. 즉, 단위연산이 n번 수행되고 이에 따라 최악의 경우 분석의 시간 복잡도는 $W(n) = n$이다.

 

참고로, 순차 검색의 경우 입력된 배열의 값에 따라 검색하는 횟수가 달라지기 때문에 입력 값에 종속되지 않는다는 모든 경우 분석의 조건을 만족하지 못하게 되며 이에 따라 모든 경우 분석은 불가능하다.

 

3. 평균의 경우 분석 (Average-case analysis)

입력 값과 입력 크기 모두에 종속되어 있는 경우로, 모든 입력에 대해 단위연산이 수행되는 평균 횟수(기대치)를 의미한다. 각 입력에 대해 확률 할당이 가능하며, 최악의 경우보다는 계산이 복잡한 것이 특징이다.

 

예시 : 순차검색 알고리즘

(1) 입력크기 : 배열의 원소 개수 ($len(S) = n$)

(2) 단위연산 : 배열의 각 값과 x(찾고자 하는 값)값의 비교

(3) 가       정 : 배열의 아이템은 모두 다르다

x = 4
S = [1, 2, 3, 4, 5]
cnt = 0

for i in S:
    if i == x:
        break;
    cnt += 1

 

1) Case 1 : x가 배열 안에 있는 경우

$$ A(n) = \sum_{k=1}^n k \times \frac {1} {n} = \frac {n + 1} {2} $$

• $1 \leq  k leq n$ 에 대해 $x$가 배열의 $k$번째에 있을 확률 $= \frac {1} {n}$
• $x$가 배열의 $k$번째에 있을 때, 이를 찾기 위해 수행하는 단위연산 횟수 $= k$

2) Case 2 : x가 배열 안에 없는 경우를 고려

$$ A(n) = \sum_{k=1}^n (k \times \frac {p} {n}) + n(1-p) = n(1 - \frac {p} {2}) + \frac {p} {2} $$

• $x$가 배열 $S$ 안에 있을 확률 = $p$
• $1 \leq  k \leq n$ 에 대해 $x$가 배열의 $k$번째에 있을 확률 $ = \frac {p} {n}$
• $x$가 배열에 없을 확률 = $1 - p$
• $x$가 배열의 $k$번째에 있을 때, 이를 찾기 위해 수행하는 단위연산 횟수 $= k$

4. 최선의 경우 분석 (Best-case analysis)

입력 값과 입력 크기 모두에 종속되어 있는 경우로, 모든 입력에 대해 단위연산이 수행되는 횟수가 최소인 경우를 선택하는 방법이다.

 

예시 : 순차검색 알고리즘

(1) 입력크기 : 배열의 원소 개수 ($len(S) = n$)

(2) 단위연산 : 배열의 각 값과 x(찾고자 하는 값)값의 비교

x = 4
S = [1, 2, 3, 4, 5]
cnt = 0

for i in S:
    if i == x:
        break;
    cnt += 1

 

찾으려는 값($x$)이 배열의 가장 앞에 존재할 때, 입력의 크기에 상관없이 단위연산이 한 번만 수행된다.

따라서, $B(n) = 1$