'컴퓨터 사이언스'에 해당되는 글 1건

  1. 2016.12.06 [컴퓨터 공학] 점근 표기법 (Asymptotic Notation) 1
2016. 12. 6. 18:02

안녕하세요. 게임개발자 놀이터 입니다.


이번 포스팅에선 알고리즘 수행 시간을 분석하는 방법중 하나인 점근 표기법에 대해 포스팅 하려고 합니다.


대부분의 알고리즘은 입력된 크기가 작으면, 알고리즘의 효율과 상관 없이 빨리 끝납니다.


하지만 입력된 크기가 크면, 속도에 차이가 나게 됩니다. 그래서 알고리즘의 수행시간을 분석할 때는 항상 입력의 크기가 충분히 클때에 대해서 분석 합니다. 이를 점근적 분석 이라고 합니다.


대표적으로 5가지 표기법이 있습니다.

  • 대문자 O 표기법 ( 빅 오 표기법 )
  • 소문자 o 표기법 ( 리틀 오 표기법 )
  • 대문가 오메가(Ω) 표기법 ( 오메가 표기법 )
  • 소문자 오메가(ω) 표기법 ( 리틀 오메가 표기법 )
  • 대문자 세타(Θ) 표기법 (세타 표기법 )


하나씩 적어 보도록 하겠습니다.


대문자 O 표기법 ( 빅 오 표기법 )


빅 오 표기법은 컴퓨터 공학에서 알고리즘의 복잡도 또는 성능을 표현하기 위해 사용됩니다.

빅 오 표기법은 특히 최악의 경우를 표현하며, 알고리즘의 실행 시간이나, 사용 메모리 (메모리, 또는 디스크) 공간을 표현 하기도 합니다.


O(1)

O(1) 은 알고리즘의 실행시간 (또는 공간)이 입력되는 데이터의 크기에 상관 없이 항상 같은경우를 의미합니다.


1
2
3
4
5
6
7
8
bool IsNull(int[] intarrays)
{
    if (intarrays == null)
    {
        return true;
    }
    return false;
}
cs


위와 같은 경우 입력된 intarrays의 크기와 상관없이 if문 한번만 실행됩니다. 그래서 데이터의 크기에 상관없이 항상 같습니다.


O(N)

O(N)은 입력되는 데이터의 양에 따라 비례하여 처리 시간이 증가하는 경우를 의미합니다.

1
2
3
4
5
6
7
8
9
10
11
bool IsNull(int[] intarrays, int index)
{
    for(int i = 0; i < intarrays.Length; ++i)
    {
        if (intarrays[i] == index)
        {
            return true;
        }
    }
    return false;
}
cs


위와 같은 알고리즘의 경우 중간에 intarrays[i]와 index값이 같아 빠져나갈수도있습니다. 하지만 빅 오(Big O)는 최악의 경우에 대한 성능을 나타낸다는것을 기억해야합니다. 즉 항상 최대로 반복이 이뤄질경우를 상정한 한계값을 표시하는겁니다.


O(N²)

O(N²)는 수행 성능이 입력 데이터의 크기의 제곱승에 비례하여 증가하는 상황을 표현합니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool IsNull(int[] intarrays, int index)
{
    for(int i = 0; i < intarrays.Length; ++i)
    {
        for(int j = 0; j < intarrays.Length; ++j)
        {
            if (intarrays[j] == index)
            {
                return true;
            }
        }
    }
    return false;
}
cs


이는 일반적으로 중첩된 반복문이 주어딘 데이터값들에 대해 수행하는 경우에 해당됩니다. 좀더 많은 반복문이 있다면 O(N³), O(N⁴)의 결과로 나타냅니다. 


O(log N)

O(log N) (로그형 빅오) 는 입력 데이터의 크기에 따라 처리 시간이 조금씩 증가하는 경우를 표현합니다.

이진 탐색 알고리즘이 대표적이죠!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int searchint(int* intarrays, int index)
{
    int from = 0;
    int to = intarrays.Length - 1;
 
    while (from <= to)
    {
        int mid = (from + to) / 2;
 
        if (intarrays[mid] > index) 
        {
            to = mid - 1;
        }
        else if (intarrays[mid] < index)
        {
            from = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
cs


좋은 알고리즘들이 대부분 가지고있는 형태 입니다.


O(2ⁿ)

O(2ⁿ)는 입력 데이터가 하나 증가할때마다 처리 시간이 2배씩 증가하는 경우를 표현합니다. 

(으... 예제로 무슨 코드를 짜야하는거지..)


예제 코드를 짜는데 실패했습니다... 알려주세요.. (._.


O(2ⁿ)은 수행시간이 아주 빠르게 증가하여 최악의 알고리즘이라고 합니다..



빅 오 표기들을 대소로 정리하면 다음과 같습니다.

O(1) < O(log N) < O(N) < O(N²) < O(2ⁿ)




소문자 o 표기법 ( 리틀 오 표기법 )


리틀 오 표기법은 빅 오 표기법 보다 좀 더 여유있는 상한을 표현할때 사용됩니다.

알고리즘의 복잡도 또는 성능을 표기할때는 자주 쓰이지 않는 표기법입니다.


어떤 알고리즘의 분석시간이 o(log N) 이라 한다면, 이는 해당 알고리즘의 소요시간이 입력크기 N에 대해 log N보다 완만하게 증가한다는것을 뜻합니다.

이해 하기 어려웠는데, log N처럼 증가하지 않지만, log N과 비슷하게 증가한다는 뜻입니다. 즉 O(log N)과 o(log N)은 같은 증가 속도가 될 순 없고, log N보다 완만하게 증가하는것이 분명할때 사용된답니다.


대문자 오메가(Ω) 표기법 ( 빅 오메가 표기법 )


빅 오메가 표기법은 빅 오 표기법과 마찬가지로 알고리즘의 복잡도 또는 성능을 표기할때 사용됩니다.

하지만, 빅 오 표기법은 최악의 경우 를 표시 했다면, 빅 오메가 표기법은 최고의 경우를 표현합니다.


손쉽게 말하면 f(N) = Ω(2N) 이라 한다면 f(N)은 적어도 2N에 비례하는 시간이 소요됨을 뜻합니다.


해당되는 알고리즘을 실행하는데 걸리는 최소한의 시간을 나타 내는 것입니다.


이는 맨 밑에있는 세타 표기법과 동시에 설명하는게 편하니, 밑에서 예제를 들겠습니다.


소문자 오메가(ω) 표기법 ( 리틀 오메가 표기법 )


리틀 오메가 표기법은 빅 오메가 표기법 보다 좀 더 여유있는 상한을 표현 할때 사용됩니다.


제가 위에 적은 리틀 오 표기법과 비슷하죠. 맞습니다.


어떤 알고리즘의 분석시간이 ω(log N) 이라 한다면, 이는 해당 알고리즘의 소요시간이 입력크기 N에 대해 log N보다 완만하게 증가한다는것을 뜻합니다.

이해 하기 어려웠는데, log N처럼 증가하지 않지만, log N과 비슷하게 증가한다는 뜻입니다. 즉 Ω(log N)과 ω(log N)은 같은 증가 속도가 될 순 없고, log N보다 완만하게 증가하는것이 분명할때 사용된답니다.


세타(Θ) 표기법 (세타 표기법 )


세타 표기법은 빅 오 표기법은 최악의 경우, 빅 오메가 표기법은 최고의 경우를 나타낸다면, 세타 표기법은 평균의 경우를 나타내는 표기법입니다.


빅 오 와 빅 오메가의 중간이라고 생각 하시면 편합니다.


중간이라는 표현은 좀 애매한데, 빅 오 와 빅 오메가의 교집합이라 생각하십니다. 그러니까

이 알고리즘은 아무리 좋아지거나 아무리 나빠지더라도 세타 범위 안에있다. 라는 뜻입니다.


점근적 표기법에 대해 어느정도 적어봤습니다.


적다 보니 빅 오 를 제외하고 나머지 4개 표기법에 대해서는 완벽하겐 모르겠네요.


앞으로 이 5개를 각각 1개 씩 나눠서 포스팅을 해야겠습니다.


감사합니다.


'프로그래밍 > Computer Science' 카테고리의 다른 글

[TCP/IP] TCP 3-way Handshake  (0) 2016.12.14
Posted by 시리시안