big-O 개념 이해하기.

big-O란 무엇일까?

시간 복잡도(점근적 실행 시간)와 공간 복잡도를 표현하는 방법이다.

---

이 책에서는 이 big-O 개념이 상당히 중요하다고 말한다. 그리고 넘어가면서 예제를 통해 big-O를 구하는데 생각 이상으로 만만치가 않다.(일부 문제는 해설도 이해가 잘 안된다.;;;)

big-O는 한번에 끝내기 어려운 듯 하여 여러 챕터에 나누어서 올려보려고 한다. 우선 개념적 이해부터 시작하자.

 

수학적 정의.

어떤 양의 상수 c와 k가 존재하여 모든 n > k에 대하여 f(n) ≤ c∙g(n) 이면 f(n) ≤ O(g(n)) 이다.

 

알고리즘에서의 big-O의 의미.

big-O 시간은 알고리즘의 효율성을 나타내는 지표 혹언 언어.(책 내용.)

 

⒈ 우선 수학적 정의를 살펴보자.

먼저 상수 c, k의 의미가 궁금할수 있다. 그리고 f(n)과 g(n)의 의미도 궁금할 수 있다.

 1.) f(n)은 실제 알고리즘의 수행 시간을 표현한 수식이다.

//오늘의 예제 알고리즘
void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + " , " + array[j]);
        }
    }
    
    for (int i = 0; i < array.length; i++) {
    	system.out.println("hi i'm " + i);
    }
    
    system.out.println("The End");
}

위와 같은 함수가 있다고 할 경우 이 함수의 f(n)을 구하는 과정은 이렇다.

array의 길이가 n 일 경우 바깥의 for문이 n번, 안쪽 for문이 n번 돌게된다. 즉, 중첩 for문 안에 있는 print문은 n * n번 수행을 하게 된다.(n²)

그리고 두번째 for문 내 print문은 array의 길이만큼(n번) 출력이 되고(n) 마지막 print문은 한번만 출력된다.(1)

결국 함수의 f(n)은 n² + n + 1이 된다.(쉽게 생각해서 반복문의 중첩은 곱셉, 별도 수행은 덧셈으로 처리하면 된다.)

f(n) = n² + n + 1

 

 2.) g(n)은 함수의 수행시간을 정의하는 가장 지배적인 항만 남긴 수식이다.

결국 g(n)은 구하고자 하는 big-O수행시간의 수식이다.

위 수식을 다시 가져와 보자.

f(n) = n² + n + 1 = n∙(n + 1) + 1

이 수식에서 n이 증가함에 따라 두개의 1은 상수로 수행시간 증가에 영향이 없다보 보고 제외한다.

그렇게 되면 이 수식에서 g(n)은 남은 n²가 된다.

g(n) = n²

 

 3.) "어떤 양의 상수 c와 k가 존재하여 모든 n > k에 대하여 f(n) ≤ c∙g(n) 일 경우"가 무슨 말일까?

위 수식을 가지고 아래 그림을 보자.

(이렇게 그래프를 그려주는 프로그램으로 확인해보면 그래프가 교차되는 지점을 눈으로 바로 확인 가능하여 c값을 구하는게 수월하다.)

위 이미지를 보면 f(n) ≤ 2∙g(n)이 되는 지점이 x축의 1과 2 사이에 존재한다. (왜 c 자리에 2가 들어가게 되었는지 궁금하다면, 1부터 하나씩 올려가면서 그래프를 그려보면 된다. 그러면 가장 처음 교차가 일어나게 되는 양의 정수가 2이다.)

특정 양의 상수값(k)보다 큰 x값이 주어졌을 때 f(n) ≤ c∙g(n) 이 공식이 성립하는 지점. 그 값이 k이다. 이 식에서는 k가 1, c가 2이면 모든 n > k 에 대하여 모든 f(n) ≤ c∙g(n)이 성립한다.

(달리 말해보겠다. 그래프의 교차가 일어나는 c값을 먼저 찾고, 그 교차가 일어나는 지점의 x값에서 소숫점을 버린 정수가 k가 된다.)

그러므로 f(n) ≤ O(g(n²))이 된다.

 

⒉ 알고리즘에서의 big-O의 의미를 살펴본다.

사실 이 부분이 개발자가 봐야하는 중요한 부분인 것 같다. 수학적 정의야 그냥 사이드 지식으로 챙겨두고 그렇구나 하는 정도로 넘어가도 될 것 같다.

우리가 big-O를 살펴봐야 하는 이유는 알고리즘이 주어졌을 때 최악의 수행시간을 구해야 하기 때문이다. 하지만 이게 어렵게 느껴졌던 이유는 f(n)을 통해서 g(n)을 구하는 과정에 "대략"이라는 개념을 넣어야 하기 때문이다.

위 수식을 가지고 그래프를 통해 한번 확인해보자.

(좌측은 매우 가까이서 살펴본 그래프. 우측은 매무 멀리서 바라본 그래프의 모양)

이 그래프를 보면, x가 커질 때 Y의 값이 서로 비슷하게 진행된다. 아까 위에서 언급했지만, 대략적인 최악의 시간을 찾는것이기에 전체적인 큰 방향성에 큰 영향을 끼치지 않는 상수 1과 x는 제외한다.  그렇게 오늘의 예제 알고리즘의 시간 복잡도는 O(g(n²))이 된다. 그런데 일일이 이렇게 그래프를 그려가며 확인 할 수도 없는 노릇. 그럼 기준을 정해보자.

 

 - 상수항은 무시하라.

 - 지배적이지 않은 항은 무시하라.( 단, 항과 항 사이에 특별한 관계가 없다면 무시하면 안된다.)

 

예를들어 아래와 같은 코드가 있다.

//오늘의 두번째 예제 알고리즘
void printPairs2(int[] array1, int[] array2) {
    for (int i = 0; i < array1.length; i++) {
        for (int j = 0; j < array2.length; j++) {
            System.out.println(array1[i] + " , " + array2[j]);
        }
    }
    
    for (int i = 0; i < array2.length; i++) {
    	system.out.println("hi i'm " + i);
    }
    
    system.out.println("The End");
}

우선 이 수식의 f(n)을 구해보자.

array1의 길이는 a, array2의 길이는 b이다.

그러면 수식은 a∙b + b + 1이다.(왜 이렇게 되는지는 수학적 접근에서 언급하였다.) 이 식을 변형해 보면 b∙(a + 1 ) + 1 이 된다.

f(n) = a∙b + b + 1 = b∙(a + 1 ) + 1

여기에서 두개의 상수 1은 수식에 큰 영향이 없음으로 제외시킨다. 그러면 a∙b만 남게 된다.

즉, 위 함수의 시간 복잡도는 a∙b이다.

g(n) = a∙b
f(n) ≤ O(a∙b)

 

시간복잡도를 구하는 것에 핵심는 f(n)을 어떻게 정확하게 구하는가 인것 같다.(내 생각)

이 부분과 공간 복잡도에 대한 이야기는 다른 글에서 이야기 하겠다.

 

사실 책을 보면서도 이해하기 어려웠는데, 블로그 쓰려고 그래프로 그려도 보고 수학적 정의도 다시 검색해 보고 하다 보니 조금은 이해가 된 것 같다. 하지만, 실제 알고리즘의 f(n)을 구하고 big-O를 구하는 과정은 이제부터 연습을 해야하는 부분이다. 단순 프린트문이 아니라 여러줄의 수식이 들어있고, 재귀함수 등 고려해야할 사항이 많이지게 되면 점점 헷갈리게 된다. 나도 책의 예제를 보는데 가장 어려운 것이 f(n)을 구하는것이었다. 해설을 봐도 또 검색해봐야하는 수고(?)가 있긴 하지만 조금 더 정확한 개념을 가지고 시간 복잡도를 좀 더 정확하게 구할 수 있는 실력이 될 때 까지 계속 공부하자. 아즈아~!!!

 

(틀린내용이 있다면 댓글로 달아주세요. 수정하도록 하겠습니다~)