Big O notation, 점근표기법과 시간복잡도

시간 복잡도, 공간 복잡도를 이야기하기에 앞서 표현되는 수식에 대한 이해가 필요하다.

가장 기본적으로 컴퓨터 과학(CS)이라는 분야는 다른 과학들처럼 수학을 기본으로 하고 있다는 것을 유념해야 한다.

 

---

 

1. 점근 표기법

 

결과를 쉽게 계산하기 어려운 두 함수가 있다고 하자.

두 함수는 같을수도 있고 다를수도 있다.

함수 간의 해석은 다양한 방법으로 이루어지는데, Big O notation 은 증감양상을 기준으로 관계를 파악한다.

 

중요한 것은 증감 양상이다.

 

x 값과 무관하게 값이 변하지 않는다.

위와 같은 식이 있다고 하자.

함수 f 에 0이 오든, 100 이 오든 결과는 늘 상수값을 갖는다.

g 역시 마찬가지다.

이들을 우리는 상수함수라고 한다.

 

상수함수는 미분하면 기울기를 갖지 않으므로 유의미한 결과를 가질수는 없다.

마찬가지로 복잡도라는 개념에서도 외부 입력이나 내부 처리에 따라서 명령을 실행하는 횟수가 달라지지 않는 경우이다.

 

 

 

x 값이 무한히 커지거나 무한히 작아진다면?

이번에는 각 함수 f 와 g 는 포물선을 그리며 기울기를 갖는다.

함수 f 에 1을 넣게 된다면, 519 가 될 것이다.

g 는 -1195쯤 될 것이다.

여튼 작은 수가 들어갔을 경우, 두 함수는 매우 큰 차이를 나타낸다.

 

문제는 증감량이다.

매우 크거나 매우 작은 값이 오는 경우, 두 함수의 차이를 배율로 본다면 어느정도가 될까?

 

우선 x 가 0일 경우,

f 는 500, g 는 -1000 이고

x 가 1일 경우,

f 는 519, g 는 -1195 이다.

 

0 -> 1로의 변화량은

각각 19, -195 이고

f와 g 의 증감량의 변화는 

|500| : |-1000| = 1 : 2 에서 |519| : |-1195|=1 : 2.302 쯤 된다.

 

x 에 100을 넣어보자.

f 는 2002200 이 되고, g 는 2999000 이 된다.

0 -> 100 으로 변화량은

각각 2001700, 3000195 이다.

f 와 g 의 증감량의 변화는

|500| : |-1000| = 1 : 2 에서 |2002200| : |3000195| = 1 : 1.4984 쯤 된다.

 

절대량은 무조건 함수 g 가 큰 폭으로 떨어졌다가 올랐다가 변화하게 된다.

그러나 증감량은 1:2 -> 1:1.49 로 점점 줄어드는 것을 알 수 있다.

만일 무한한 값으로 입력값을 주게 된다면, 두 함수는 결국 거의 유사한 변화량을 갖게 된다.

(더 큰 값들을 비교 실험하셔도 됩니다. 1은 되지 않지만 점점 1에 수렴하게 됩니다.)

 

두 함수가 최고차항의 지수를 보고 그 값이 동일하다면 증감량의 변화량은 유사하다.

 

이를 가지고 부가적인 다른 수식을 모두 계산하지 않고 간단히 아래처럼 표기하는 방법을 점근 표기법이라고 한다.

 

한쪽을 입증하면 반드시 반대쪽도 증명되는 것은 아니라는 것을 일단 기억하자.

위 수식에서는 equal 기호를 사용했지만, 엄연히 보면 삼단논법에 의해 함수 f 와 g 가 같다라는 오류를 범할 수 있다.

표기는 저렇게 하지만, 같다라는 표기보다는 포함된다라고 보는 것이 보다 이해가 쉽다.

 

---

 

2. 시간복잡도

 

점근 표기방식을 이용하여 컴퓨터 과학에서는 효율성, 수행시간을 어림짐작 할 수 있다.

 

OS 를 직접 튜닝하여 프로세스 처리방식을 바꾸지 않는다는 가정하에

두 프로그램(함수)은 하나의 명령에 하나의 동일한 실행시간을 가진다고 가정한다.

(물론 실제로는 어셈블하면 단일명령과 복수명령으로 나뉘거나 참조테이블을 생성하는 등 다양한 차이가 있으나 잊자)

 

그렇다면 동일한 기능을 수행하는 두 프로그램 중, 명령을 많이 수행하는 프로그램은 그렇지 않은 프로그램에 비해 효율성이 낮다 혹은 시간복잡도가 높다라고 할 수 있다.

 

다만 이 역시 단순히 절대치를 가지고 이야기하는 것이 아니다.

사용자의 입력이나 데이터, 반복문 등에서 입력에 따른 수행시간의 증감량을 더 중요하게 보게 된다.

 

앞서 점근표기법에서 이야기한 두 함수 f 와 g 를 보면,

당장 작은 입력값에 대해서는 f보다 g 가 cost 가 적다. (심지어 음수로 시작한다.)

다만 입력이 100 정도만 되어도 g 는 더 높은 cost 를 갖게 된다.

이윽고 입력이 매우 큰 값이 된다면, f 나 g 나 거의 비슷한 cost 를 갖게 될 것이다.

 

 

최적화라는 관점은 바로 이러한 cost 를 얼마나 적게 가져갈 수 있느냐에 관점을 둔다.

 

함수 f 와 g는 O(N^3) 이라는 시간복잡도를 갖게 된다.

 

        private int solution(string[] args)
        {
            int rst = 0;
            foreach (var item in args)
            {
                foreach (var code1 in item)
                {
                    foreach (var code2 in item)
                        rst++;
                }
            }
            return rst;
        }

위 주어진 코드는 점근 표기법의 함수 f 와도 같은 시간복잡도를 갖는다.

심지어 C# 의 LinQ 를 이용하더라도, 최적화를 생각하지 못한다면 위와 별반 다르지 않은 코드가 완성될 것이고

데이터 량이 그렇게 크지 않음에도 하염없이 사용자를 대기하게 만드는 프로그램이 완성될 수 있다.

 

같은 코드를 짜더라도 다음과 같이 짜면 보다 적은 시간복잡도를 갖게 된다.

        private int solution(string[] args)
        {
            int rst = 0;
            foreach (var item in args)
            {
                rst += item.Length;
            }
            return rst;
        }

 

사실 위에 예시들은 썩 좋은 예시들이 아니다.

너무나 당연한 코드를 나열하였으니까.

 

실제로 최적화문제를 만나는 일들은 사용자 입력에 유의미한 의미들이 부여되거나 코드 평면화가 어려운 경우이다.

또는 이미 개발되어 상용화된 프로그램에 오랜기간 많은 개발자가 다녀간 흔적이 남은 그야말로 이제는 새롭게 만들어야 하지 않을까? 싶은 그런 소스들도 있다.

아니면 동료 개발자가 최근 배워온 머지소트가 인상깊었던지 Vector 나 맵으로 O(N) 회만 돌면 되는 XML 문자 파싱을 스스로 만들겠다고 파고들어 O(N logN) 으로 레벨업 시켜주거나 대표, 또는 책임에 의해 방어로직이 추가되면서 구태여 검사가 필요하지 않았던 리소스를 만지게 되면서 도리어 평소에는 효율성을 극감시키는 형태로 개발이 이루어 질 수도 있는 것이다.

 

그냥저냥 짜는대로 가다가는 사용자에게 적정대기 시간 이상을 요구하는 꼴이 나 버린다.

 

---

 

프로그래머는 그냥 되는대로 개발을 하는 것이 아니라

동일한 조건이라면, 보다 효율적이고 cost가 적은 최적화된 개발을 해 나가는 것이 바람직하다.