본문 바로가기
language/java

Algorism의 복잡도

by vamalboro 2008. 1. 21.
복잡도 (시간복잡도, 공간복잡도)

복잡도를 나타낼 때에 자주 사용되는 함수

증가율

낮음 ◀----------------------------------------------------------------------------▶높음
   1          log n          n          n log n          n^2          n^3          n^4          n^k‥‥     2^n

예)
int[] a = new int[100];
int[] b;
// a배열에 값 입력
b = a; << 이 대입문의 복잡도는 레퍼런스변수의 주소값 복사이므로 O(1)이다

보통 실제로 사용가능한 알고리즘은 다루는 데이터의 양에 따라 다르지만, 복잡도가

O(1), O(log n), O(n), O(n log n), O(n^2) 정도이다.


선형탐색과 이진탐색의 검색시의 시간 복잡도를 구해보자.

[선형탐색]

public Object search(int key) {
    int i;
   
    i = 0;                                     // (1)
    while(i < n) {                        // (2)
        if (table[i].key ==  key)       // (3)
            return (table[i].data);     // (4) 발견시 한번
        i++                                   // (5)
    }
    return null;                            // (6) 발견하지 못했을때 한번
}

             실행회수     복잡도
(1)번           1            O(1)
(2)번         n/2           O(n)
(3)번         n/2           O(n)
(4)번           1            O(1)
(5)번         n/2           O(n)
(6)번           1            O(1)

검색알고리즘의 시간복잡도는 각 행의 복잡도의 합을 구하면 된다

(2), (3), (5)는 모두 O(n) 이니 O(n) + O(n) + O(n) = O(n)이다.

총 합은 (1), (4), (6)는 모두 O(1) 이니 O(1) + O(1) + O(1) 에 위 복잡도를 합하여

search 메소드의 복잡도 = O(1) + O(1) + O(1) + O(n)
                                  = O(max(1,1,1,n))
                                  = O(n) 이다.

즉 선형탐색은 탐색을 1회 실행하는데 테이블에 등록되어있는 데이터의 개수에 비례한
시간이 걸리게된다.



[이진탐색]
<오름차순으로 정렬되있는 데이타 배열에서>
public Object search(int key) {
    int low, high, middle;

    low = 0;                                          // (1)
    high = n - 1;                                   // (2)

    while(low <= high) {                       // (3)
        middle = (low + high) / 2;            // (4)
        if (key == table[middle].key)        // (5)
            return table[middle].data;       // (6)
        else if (key < table[middle].key)  // (7)
            high = middle - 1;                  // (8)
        else // key > table[middle].key 
            low = middle + 1;                   // (9)
    }
    return null;                                    // (10)
}


            실행회수     복잡도
(1)번           1            O(1)
(2)번           1            O(1)
(3)번         (4) ~ (9)의 복잡도를 합한것이 된다.(실행횟수또한마찬가지)
(4) ~ (9)     루프 한번당 각 행은 최대 한번씩 실행되며 복잡도는 O(1)이다
(10)번         1             O(1)

위 (3)번의 실행횟수는 O(log n)이다. (이진탐색은 한번 탐색시마다 반씩 쪼개어 탐색되어지기때문에)

결국 (3) ~ (9)의 복잡도는 루프내부의 복잡도((4)~(9)) O(1) * O(log n)  = O(log n)이다.

총 search메소드의 복잡도는

O(1) + O(log n) + O(1) = O(max(1, log n, 1))
                                = O(log n) 이다

선형탐색과 이진탐색의 데이타 등록시의 복잡도

[선형탐색]

public void add(int key, Object data) {
    if (n >= MAX) {
        // error 처리
    }
    table[n++] = new Entry(key, data);
}
위의 각 행들은 O(1)이다 . 선형탐색에서의 데이타 등록 처리의 복잡도는 명확히 O(1)이다.

[이진탐색]

public void add(int key, Object data) {
    int pos;

    pos = 데이터를 삽입할 위치;                         // (1)

    배열에서 pos보다 뒤에 있는 요소들을 모두 1씩 민다;  // (2)
 
    table[pos] = new Entry(key, data);                  // (3)
}

(1)행은 삽입할 위치를 찾기위해 이진탐색을 하므로 O(log n)이다
(2)행은 평균 n/2개의 데이터를 이동할 필요가 있으므로 O(n)이다.
(3)행은 O(1)이다

전체 데이타를 등록하는
add메소드의 복잡도 = O(log n) + O(n) + O(1)
                            = O(max(log n, n, 1))
                            = O(n) 이다

즉 이진탐색의 데이타 등록의 복잡도는 테이블에 등록된 요소의 개수n에 비례한다.

데이타의 1개요소일때는 O(n)이지만 n개 요소일때는 O(n2) 이다.

이 시간 복잡도를 줄일 수 있는 방법으로 등록시에 선형탐색과 같이 등록순서대로 등록후 O(n)

정렬하는 방법이 있다.

정렬알고리즘에는 복잡도가  O(n log n)인 것이 있기 때문에 결과적으로

이진탐색의 데이타 등록의 전체복잡도는

O(n)등록 + O(n log n)정렬 = O(max(n, n log n))
                                     = O(n log n) 으로 줄일 수 있다.

결론적으로 이진탐색은 '프로그램의 실행 중에 빈번한 데이터 등록을 하면서 동시에 탐색을 한다'
 라는 경우에 사용하는 것은 적절치 않다.




                                                                                         - 2008.01 15:27 -