[자료구조] 03. Big-O 표기법

본 내용은 필자가 학부 자료구조 수업내용을 공부하기 위해 정리한 것임을 알려드립니다.

2-3. Big-O 표기법

• f(n) = O(g(n))
• 입력의 크기가 무한히 커질 때, 입력이 특정한 입력(n0)보다 크기만 하면 f(n)은 항상 M * g(n) 보다 작거나 같다를 만족하는 특정한 입력(n0)과 M이 존재한다.
• f(n) <= g(n)
• f(n) <= g(n) for n0 < n
• f(n) <= M*g(n) for n0 < n
  • 동일한 비율로 증가하는 함수를 허용하기 위해 상수 M을 허용한다.

성질 1

어떤 n > n1 에 대해서 g1(n) < g2(n) 이라면 f(n) = O(g1(n))은 f(n) = O(g2(n))을 의미한다.

• f(n) = O(g(n))이고, g1(n)보다 g2(n) 함수가 더 성능이 좋지 않을 때, f(n)의 입장에서도 g2(n)은 upper bound다.

성질 2

어떤 상수 k에 대해서 f(n) = O(k*g(n))이라면, f(n) = O(g(n))이다.

• k는 생략 가능하다.

성질 3

f(n) = O(g1(n) + g2(n))이고, 어떤 n > n1에 대해서 g1(n) < g2(n)이라면 f(n) = O(g2(n))이다.

• 두 함수 중 낮은 계수는 생략되고, 높은 계수(성능이 좋지않은)가 곧 빅 오 표기법 함수로 대표된다.

빅 오메가(Big-Omega) 표기법

• 빅 오 표기법과 반대되는 의미
• f(n) = O(g(n)) 일 때, g(n) = Ω(f(n))
• g(n)은 f(n)보다 느리다.
• g(n)의 lower bound는 f(n)이다.

빅 세타(Big-Theta) 표기법

• 동일한 n에 따라 f(n)과 g(n)이 서로 근사치의 비율로 증가할 때
• f(n) = O(g(n)) 과 g(n) = O(f(n)) 일 때.
• f(n) = Θ(g(n))

---

2-4. Big-O 표기법의 예

상수 시간 복잡도 (constant time complex)

• f(n) = O(1)
• 반복문을 이용한 별 찍기 보다 printf("*")를 이용한 별 찍기가 효율이 좋다!(?)
• 입력이 증가해도 일정한 시간이 걸린다.
• 가장 이상적인 성능

void f(int n) {
    printf("Hello");
}

선형 시간 복잡도(linear time complex)

• f(n) = O(n)
• 시간은 입력의 크기(n)에 비례한다.
• for-loop와 while문

void f(int n) {
    i=0;
    while (i < n) {
        printf("hello");
        i++;
    }
}

다항 시간 복잡도(Polynomial time complex)

• f(n) = O(n^k) if k=2
• f(n) = O(n^2)
• 시간은 입력의 크기의 k제곱에 비례해서 증가한다.
• k=2 일때 삽입, 버블, 선택 정렬 시간복잡도

void f(int n) {
    for (i=0; i<n; i++){        //외부 loop O(n)
        for (j=0; j<n; j++) {   //내부 loop O(n)
            printf("hello");
        }
    }
}                               //총 O(n^2)번 수행

지수 시간 복잡도(exponenetial time complex)

• f(n) = O(k^n) k=2
• f(n) = O(2^n)
• 시간은 k의 n제곱에 비례해서 증가한다.
• 매우 매우 매우 좋지 않은 시간복잡도
• k=2 일때 피보나치 수열, 높이가 n인 tree에서 전체 노드의 갯수

/// 토끼의 수 : f(n) = f(n-1) + f(n-2)
int f(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return f(n-1) + f(n-2);
}

• 피보나치 수열은 자기 자신을 이용해 개념을 정의한다.
• 따라서 Recursive(재귀적으로)로 구현한다.
• 입력받은 n이 0이거나 1이 아닌 경우 f(n-1) + f(n-2) 계산값을 return 한다.
• 입력 값이 높아질 수록 피보나치 수열을 계산하기 위해 불필요한 계산이 많아진다.
  • n=6일 뿐인데 함수 호출 수는 25번이다.
• f(n)이 불리는 횟수 = 2^n 번

로그 시간 복잡도(log time complex)

• f(n) = O(log n)
• 시간은 n의 log에 비례해서 증가한다.
• 밑(k : base)는 생략
  • 로그의 base에 따라 성능에 영향을 주긴 하지만 그 차이는 알고리즘 성능에서 매우 미미한 차이기 때문에 생략이 가능하다.

int f(int n) {
    for (k=1; k<n; k = k*10) {
        printf("hello");
    }
}

• k가 1,2,3…씩 증가할 때마다 코드는 1번, 10번 100번, 10000번…수행된다.
• 만약 입력 값이 1경정도라면 해당 코드에서 15번 loop시 수행이 끝나는 최강의 성능을 보여준다.

nlogn 시간 복잡도(nlogn time complex)

• f(n) = O(nlogn)
• O(n) 보단 느리고 O(n^2)보단 빠른 성능

void f(int n) {
    for (i=1; i<n; i++) {           // outer loop O(n)
        for (j=1; j<=n; j*=10) {    // inner loop O(logn) 
            printf("hello");
        }
    }
}

---

결론