[Journal] 점근표기법과 시간복잡도

big O notation과 little o notation에 대해 찾아보던 중, 우리가 정보과학 분야에서 자주 사용하는 시간 복잡도 개념이 이것을 응용했다는 것을 알 수 있었다. 이에 대해 자세히 조사 해 보았다.

 

---

 

이론적 배경

 

(1)    점근표기법

점근표기법이란 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법이다. 알고리즘의 시간 복잡도를 단순화 할 때나 무한급수의 뒷부분을 단순화 할 때 사용한다. 대표적으로 아래 다섯가지 표기법이 있으며, 이 보고서에서는 Big O Notation과 Little o Notation을 다룬다.

 

간단한 다항식을 예로 들어보자.

 

 

(2) 시간 복잡도

시간 복잡도란 함수로서 작동하는 알고리즘을 취해 시간을 정량화 하는 것이다. 대부분의 경우 Big O Notation을 사용하는데, 최악의 테스트케이스로 실행하였을 때 런타임 에러가 발생하지 않아야 하기 때문이다. 대부분의 경우 총 실행횟수에 서 계수와 낮은 차수의 행을 제외한 값을 시간 복잡도 O(N)로 사용한다.

예를 들어 단일 for문은 시간 복잡도가 O(N)이고, 이중 for문은 시간 복잡도가 O(𝑛^2)이며, 이분탐색의 시간 복잡도는 O(log N)이다.

 

---

 

시간 복잡도의 개념을 이해하기 위한 예제를 만들었다. 아래와 같은 코드가 주 어졌을 때 Big O Notation 시간 복잡도를 A, B를 이용해 나타내자.

 

#include <iostream>
#define A 100
#define B 50

int main() {
    int count = 0;
    int a = A;
    int b = B;
    
    while (a > 0) {
        for (b = B ; b > 0 ; b /= 2) {
            for (int c = 0 ; c < b ; c++) {
                count += 1;
            }
        }
        for (b = B ; b > 0 ; b --) {
            count += 1;
        }
        a /= 2;
    }
    
    return 0;
}

 

문제풀이 순서는 다음과 같다. 첫째, 코드를 분석하여 총 실행횟수를 A, B에 대한 점화식으로 나타낸다. 둘째, 얻은 점화식에서 Big O Notation 시간 복잡도를 구 한다. 셋째, 시간 복잡도를 옳게 구했는지 확인한다.

 

---

 

        for (b = B ; b > 0 ; b /= 2) {
            for (int c = 0 ; c < b ; c++) {
                count += 1;
            }
        }

 

18~22행의 이중 for문을 보자. 𝑂(𝐵^2)처럼 보이지만, 반복 조건이 등차가 아니므로 점화식을 구해야 한다. 계산의 편의를 위해 𝐵=2^𝑛(𝑛∈N)으로 정의했다.

 

 

        for (b = B ; b > 0 ; b --) {
            count += 1;
        }

 

23~25행은 단일 for문이며, 등차이므로 시간 복잡도는 𝑂(𝐵)이다.

 

    while (a > 0) {
        O(B)
        O(B)
        a /= 2;
    }

 

총 탐색 범위인 17~27행을 보자. a값이 절반으로 감소하기를 반복하기 때문에  탐색 횟수 𝑘는 아래와 같은 식을 만족한다.

2^𝑘 = 𝑎

따라서 while문의 시간 복잡도는 𝑂(log𝐴)이다. (시간 복잡도에서는 로그의 밑을 10으로 통일한다.)

While문 안에 O(B) 2개가 포함되어있다. 따라서 전체 시간 복잡도는 계수 2를 생략하고 𝑂(Blog𝐴)이다.

 

---

 

점근표기법이 무엇인지 알 수 있었고, 이에 대한 증명 과정이 엡실론-델타 방법과 유사 하다는 것을 느꼈다. 같은 정의를 정성적으로, 수식으로, 엡실론-델타 방법으로 표현하는 것으로 다양한 수학적 언어를 알 수 있었다.

지금까지 배웠던 정보과학에서 수학이 사용된 사례는 수학적 원리를 코드로 구현하는 것에 그쳤다. 수학적 원리를 코드로 구현하는 것이 아닌, 코드의 원리를 수학적으로 해석 한다는 점이 새롭게 다가왔다.