[알고리즘 분석] 1장. 효율, 분석, 그리고 차수 (4)

1. 알고리즘 분석 => 공간 복잡도 분석, 시간 복잡도 분석

1) 공간 복잡도(space(memory) complexity) 분석

- 입력 크기에 따라서 작업공간(메모리)이 얼마나 필요한 지 분석

2) 시간 복잡도(time complexity) 분석

- 입력 크기에 따라서 단위연산이 몇 번 수행되는 지 분석

※ 시간 복잡도가 공간복잡도보다 더 알고리즘 분석하는데에 많이 쓰인다. 

 

2. 분석 방법의 종류

1) 모든 경우 분석(every-case analysis)
- 입력 크기에만 종속하고 입력값과는 무관하다.
- 입력 값과는 무관하게 결과 값은 항상 일정함
ex. n개의 자연수를 단순 더할 때

2) 최악의 경우 분석(worst-case analysis)
- 입력 크기와 입력 값 모두에 종속
- 단위연산이 수행되는 횟수가 최대인 경우(최악)
ex. n개의 데이터에 대해 정렬 (데이터가 거꾸로 정렬되어 있을 때가 최악)

3) 평균의 경우 분석(average-case analysis)
- 입력 크기에 종속
- 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
- 각 입력에 대해서 확률 할당 가능 -> 확률 개념으로 인해 계산이 복잡해진다.

4) 최선의 경우 분석(best-case analysis)
- 입력 크기와 입력 값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우(최선)

 

※ Worst-case analysis에 더 초점을 맞추어야 한다.

 

3. '배열의 수 더하기' 시간 복잡도 분석

[ 단위 연산: 덧셈 ] -> result += S[i]
- 입력 크기: 배열의 크기 n
- 배열의 값(입력 값)과 상관없고 입력 크기에만 종속한다. -> 모든 경우 분석
- 배열의 값에 상관없이 for문을 n번 반복한다. 각 for문 당 한 번의 덧셈이 수행된다.

number sum(int n, const number S[]){
    index i;
    number result;
    
    result = 0;
    for (i = 1; i < n; i++)
        result += S[i]; // n번
    return result;
}​

- T(n) = n

[ 단위 연산: 지정문 ] -> [result = 0], [i = 1 ~ n-1], [result += S[i]]
- 입력 크기: 배열의 크기 n
- 배열의 값과 상관없음 -> 모든 경우 분석

number sum(int n, const number S[]){
    index i;
    number result;
    
    result = 0; // 1번
    for (i = 1; i < n; i++) // n번
        result += S[i]; // n번
    return result;
}​

- T(n) = 1 + n + n

 

4. '교환 정렬' 시간 복잡도 분석

[ 단위 연산 : 조건문 ] -> if (S[j] < S[i])
- 입력 크기: 정렬할 항목의 수(배열의 크기) n
- 배열의 값과 상관없음 -> 모든 경우 분석

void exchangesort(int n, keytype S[]){
    index i, j;
    for (i = 1; i <= n-1; i++)
        for (j = i + 1; j <= n; j++)
            if (S[j] < S[i]) // j 루프가 수행될 때마다 조건문 1번씩 수행
                exchange S[i] and S[j];
}​

i = 1 -> j루프 n-1번 수행
i = 2 -> j루프 n-2번 수행
...
i = n-1 -> j루프 1번 수행
-> 모든 경우의 i에 대해 조건문이 수행되는 횟수는 (n-1) + (n-2) + ... + 1 이다.
- T(n) = (n-1)n/2

[ 단위 연산 : 교환 연산 ] -> exchange S[j] and S[i]
- 입력 크기: 정렬할 항목의 수(배열의 크기) n
- exchange 연산은 if (S[j] < S[i])가 성립될 때에만 수행할 수 있으므로 최악의 경우 분석을 통해 분석한다.

void exchangesort(int n, keytype S[]){
    index i, j;
    for (i = 1; i <= n-1; i++)
        for (j = i + 1; j <= n; j++)
            if (S[j] < S[i]) // j 루프가 수행될 때마다 조건문 1번씩 수행
                exchange S[i] and S[j]; //최악의 경우일 때는 if문의 수행횟수와 동일
}​​

- 최악의 경우 -> 조건문이 항상 참일 때 -> 앞서 단위연산이 조건문인 경우에서 if문이 수행되는 횟수와 동일하다. 
- W(n) = (n-1)n/2

 

5. '행렬 곱셈' 시간 복잡도 분석

[ 단위 연산: 곱셈 ]
- 입력 크기: 행과 열의 개수 n
- 입력 크기에만 관련있기 때문에 모든 경우 분석을 통해 분석한다.

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++){
        C[i][j] = 0;
        for (k = 1; k <= n; k++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j]; // 단위 연산 -> n^3
    }​

- T(n) = n*n*n = n^3

 

6. '순차 검색' 시간 복잡도 분석

[ 단위 연산 : 배열의 아이템과 키 비교 연산 ]
- 입력 크기: 배열 안에 있는 아이템의 수 n

location = 1;
while (location <= n && S[location] != x) // 단위 연산 (비교)
    location++;
if (location > n)
    location = 0;​

- 입력 배열의 값에 따라서 비교 횟수가 달라진다 -> 모든 경우 분석이 불가능하다.
- 최악의 경우 분석: x가 배열의 마지막에 존재하거나, 배열에 존재하지 않을 때
- W(n) = n

- 평균의 경우 분석 (가정: 배열의 아이템이 모두 다르다 -> 각 배열의 아이템이 k번째 있을 확률 = 1/n)

1) x가 배열 S안에 있는 경우
$$ 1 \leq k \leq n \ 인 \ x에 \ 대해서 \ x가 \ k번째에 \ 있을 \ 확률 \ = \frac{1}{n} $$
$$ x가 \ 배열의 \ k번째에 \ 있다면 \ 수행하는 \ 단위연산의 \ 횟수 \ = k $$
$$ A(n) = \sum_{k = 1}^{n}(k\times\frac{1}{n}) = \frac{1}{n}\times\sum_{k = 1}^{n}k = \frac{1}{n}\times\frac{n(n+1)}{2} = \frac{n+1}{2} $$

2) x가 배열 S안에 없는 경우 포함
- x가 배열 S안에 있을 확률 p
- x가 배열의 k번째에 있을 확률 -> p/n
- x가 배열에 없을 확률 -> 1-p
$$ A(n) = \sum_{k = 1}^{n}(k\times\frac{p}{n}) + n(1-p) = n(1-\frac{p}{2}) + \frac{p}{2} $$
- p=1(x가 배열 S안에 있음 -> 경우 1번)을 대입하면 경우 1의 결과와 동일하게 계산된다.

- 최선의 경우 분석: x가 배열의 첫번째에 존재해서 단위연산이 1번만 수행될 때
- B(n) = 1