[자료구조] 빅-오 표기법 (Big-O Natation) - 점근 표기법 (Aasymptotic notation)

빅-오 표기법 (Big-Oh Natation) - 점근 표기법(Aasymptotic notation)

 

 빅-오 표기법 (Big-O Natation) 
 계산 복잡도 이론에서 사용되는 점근 표기법. 컴퓨터 과학에서는 주로 입력 데이터의 크기와 알고리즘의 소요 시간 또는 메모리의 상관관계를 나타내지만, 엄밀히는 임의의 함수에 대하여 "함수의 입력값(정의역의 원소)이 커짐에 따라 그 출력값(그 원소의 상)이 얼마나 빠르게 커지는가"를 표현한다. 


점근 표기법(asymptotic notation)
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

 

찾아보니 빅-오 표기법이라고도 하고 수학적으로는 점근 표기법이라고 하더군요..

프로그램을 실행했을 때 정확한 step을 확인하기는 어렵기 때문에 2n + 3 의 시간 복잡도를 가지는 경우 프로그램 실행 시에 자료가 10개라면 "20 + 3의 시간 복잡도를 가진다."라고 할 수 있는데 이 시간 복잡도로 이야기하는 것 보다 근사치의 식으로 구성해도 큰 문제가 되지 않고 큰 비율을 가지는 n이 증가함에 따라서 시간 복잡도에 영향이 크므로 n에 비례한다는 것으로 표시한다는 것으로 이해할 수 있을 것 같습니다.

시간 복잡도를 빅-오로 표기

 

 

위에 설명 처럼 가장 영향력이 있는 n의 단위로 표기합니다.

 

빅-오 표기

 

 : 데이터 수와 상관없이 연산 횟수가 고정인 유형의 알고리즘을 뜻합니다.(상수형)

int GetNumber(int number)
{
    return arry[number];
}

 

: 로그형 빅-오라고 합니다. 어느 곳에서 찾을 지 시작위치가 명확하다면,

 데이터의 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘을 의미합니다.

 이전 게시물의 이진 탐색 알고리즘이 대표적인 예 입니다.

int Search(int arr[], int length, int findNum)
{
    int first = 0;
    int end = length - 1;
    int mid;

    while (first <= end)
    {
        mid = (first + end) * 0.5;

        if (findNum == arr[mid])
        {
            return mid;
        }
        else
        {
            if (findNum < arr[mid])
                end = mid - 1;
            else
                first = mid + 1;
        }
    }

    return -1;
}

 

: 선형 빅-오라고 합니다. 데이터의 수와 처리 시간이 비례하는 1:1 관계를 의미하는 알고리즘을 말합니다.

int Search(int arr[], int length, int findNum)
{
    for (int i = 0; i < length; i++)
    {
        if (arr[i] == findNum)
            return i;
    }

    return -1;
}

 

: 선형 로그형 빅-오라고 합니다. 이는 데이터의 수가 늘때 연산 횟수가 데이터보다 조금 더 증가하는 알고리즘을 의미합니다. 대표적으로는 Heap Sort 있습니다.

void heapsort(int a[], int length)
{
  buildheap(a, length);
  int heapsize, i, temp;
  heapsize = length - 1;
  for( i=heapsize; i >= 0; i--)
  {
    temp = a[0];
    a[0] = a[heapsize];
    a[heapsize] = temp;
    heapsize--;
    satisfyheap(a, 0, heapsize);
  }
  for( i=0; i < length; i++)
  {
    cout << "\t" << a[i];
  }
}

void buildheap(int a[], int length)
{
  int i, heapsize;
  heapsize = length - 1;
  for( i=(length/2); i >= 0; i--)
  {
    satisfyheap(a, i, heapsize);
  } 
}

void satisfyheap(int a[], int i, int heapsize)
{
  int l, r, largest, temp;
  l = 2*i;
  r = 2*i + 1;
  if(l <= heapsize && a[l] > a[i])
  {
    largest = l;
  }
  else
  {
    largest = i;
  }
  if( r <= heapsize && a[r] > a[largest])
  {
    largest = r;
  }
  if(largest != i)
  {
    temp = a[i];
    a[i] = a[largest];
    a[largest] = temp;
    satisfyheap(a, largest, heapsize);
  }
}

 

: 데이터 수의 제곱 만큼 연산 횟수를 요구하는 알고리즘 입니다.

bool Equals(int arr[], int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (arr[i] == arr[j])
                return true;
        }            
    }

    return false;
}

 

: 데이터의 수의 세제곱 만큼 연산 횟수를 요구하는 알고리즘 입니다.​

 

: 상수값에 데이터의 수만큼 제곱된 만큼 연산 횟수를 요구하는 알고리즘입니다.

매우 엄청난 연산 횟수의 증가량을 보인다면, 비현실적인 알고리즘 입니다.

 

[참고]

 

- [코드] http://www.studytonight.com/data-structures/heap-sort

- [서적] 윤성우의 열혈 자료구조

- 위키 백과 - 시간 복잡도 : https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84