Big O 표기법 (Big O Notation), 시간 복잡도 표기법 (Time Complexity Notation)

안녕하세요. 연두아빠에요.

제일 먼저 앞으로 올릴 자료 구조나 기반 지식 관련 내용을 포스팅 하기에 앞서

어느 정도는 이해하고 가면 좋을 듯한 주제가 Big O 표기법인 듯 해서 가장 첫번째 포스팅으로 선정했습니다.

저 역시 컴퓨터 공학과를 복수 전공했지만, 게임을 개발하면서 Big O 표기법은 모르면 모르는데로

알면 아는데로 게임 개발 하는데 당장 큰 지장은 없었던 것 같기도 하고...

std::list가 혹은 std::map이 O (1)인지 O (n)인지 몰라도 어쨋든 계속 반복적으로 쓰다 보면 어떤 특성이 있는지

자연히 알게 되고, 언제 배열을 써야 하고 언제 list를 쓰고 언제 map을 쓰는지 감이 오게 되어 있죠.

그러나 전혀 처음 보는 자료 구조나 알고리즘들을 접하게 되는 경우, 모든 알고리즘을 일일히 벤치마킹 하며

퍼포먼스 체크를 해서 어떤 알고리즘을 사용해야 할 지 결정할 수는 없겠죠?

혹은 공식 적이거나 중요한 자리에서 본인이 만든 알고리즘의 퍼포먼스를 설명해야 하는 경우, 그냥 땀 뻘뻘 흘리며

이거 되게 빨라요 별로 느릴 만한 요소가 없어요

이렇게 촌빨 날리게 얘기하는 것 보다는 Big-O(1) 의 복잡도를 갖는다고 간단히 말해 주는게 뽀대 나지 않을까요?

Big-O 표기 법 외에도 Big-Omega(Ω), Big-Theta(Θ), Little-O, Lttle-Omega(ω) 등의 다양한 표기법이 존재하는데,

이들 모두는 결국 알고리즘의 복잡도 또는 성능을 표현하기 위한 것들입니다.

게임을 개발하며 가장 중요한 판단 기준은 무엇일까요?

그래서 이 게임으로 돈을 얼마나 벌 수 있는데?

이거 아닌가 싶은데요.

뭐, 지금은 그게 중요한게 아니고, 게임 개발에서 사용되는 알고리즘을 선정하기 위해 가장 중요한 판단 기준은

이 알고리즘이 성능이 제대로 나오겠어?

쯤이 될 텐데, 게임에선 보통 최대 빠를때 몇 초가 걸리는지 보다는 만약의 경우 무한 룹에 빠질 일은 없는지,

최악의 경우 도대체 얼마나 시간이 지체 될지가 가장 중요한 고려 대상입니다.

Big-O 표기법이 바로 이 최악의 경우에 소요되는 시간 복잡도를 표현하기 위해 사용되며,

정리하면, "최악의 상황에서도 이 정도의 성능은 보장할 수 있다" 라고 알려주기 위해 쓰인다고 할 수 있겠죠?

따라서 적어도 게임 개발에 있어서는 Big-O가 가장 중요하고 자주 사용되는 표기법일 것 입니다.

구글에서 Big-O notation 쳐보면 한글 WIKI, 영문 WIKI 얘네가 젤 앞에 나오는데...

도통 뭔 말인지 알 수 가 없고... 왠지 숨이 막혀오는 듯 하고... 여기는 어디, 나는 누구...

간단히 그래프로 표현하면 다음과 같습니다.

음... 그림을 봐도 뭐가 뭔지... 솔직히 헷갈리긴 하지만...

프로그래머라면 코드로 얘기하는 게 젤 속편할 듯 하니 간단히 꼭 필요한 내용만 코드로 정리해보고자 합니다.

O (1), O (C)

위 그래프에서 파란색 점선 화살표에 해당 되는 부분입니다.

알고리즘의 실행 시간이 입력되는 데이터의 크기에 상관없이 항상 일정한 상수 값(C)을 갖는 경우를 의미합니다.

O(1)은 1이라는 상수 시간 복잡도를 갖는 다는 의미인데, 여기서 이 1은 1초 처럼 시간을 의미하는 것이 아니라

복잡도의 기준에서 1정도의 수치를 갖는다는 것이고 프로그래밍에선 1개의 깊이로 해결 난다로 이해하면 될 듯?

자세한 건 코드를 보면 아주 쉽게 이해가 될 것으로 믿습니다.

bool IsArrayNullOrEmpty(Array array)
{
    return (null == array || 0 >= array.Length);
}

O (n)

위 그래프에서 초록색 점선 화살표에 해당 되는 부분입니다.

O(n)은 입력되는 데이터의 크기에 비례하여 처리 시간이 증가하기에 선형(Linear) 함수라고도 합니다.

아래 함수에서 배열에 1부터 10이 순차적으로 들어가있다고 가정할때 1을 검색하게 되면 당연히 바로 찾겠지만,

10을 찾거나 혹은 배열에 없는 숫자 값을 찾게 된다면, 배열을 처음부터 끝까지 다 돌아야 합니다.

자세한 건 역시 아래 코드를 보면 아주 쉽게 이해가 될 것으로 믿습니다.

bool IsContains(int[] array, int toFind)
{
    foreach(int value in array)
    {
        if (value == toFind)
        {
            return true;
        }
    }
    return false;
}

O (log n), O (log₂n)

위 그래프에서 빨간색 점선 화살표에 해당 되는 부분입니다.

O(log₂n)은 말 기수가 2인 로그 함수 형태를 띄고 있으며 그냥 간단하게 log n으로 보통 표기 합니다.

위 그래프에서 수직 성분에 해당하는 알고리즘 복잡도(Algorithm Complexity)가 데이터의 크기가

두 배 증가 할때마다 1씩 증가 하게 됩니다.

간단히 말해 데이터의 크기가 두 배 늘어나더라도 복잡도가 1씩, 아주 조금씩 증가한다는 말이죠.

그렇기에 자료의 크기와 무관한 복잡도를 갖는 O(C)를 제외하고는 가장 효율 적이라고 생각하면 될 듯.

대표적인 예로 Binary Search Tree 정도를 예로 들 수 있겠네요. 

데이터의 양이 아무리 많아도 모든 데이터를 탐색하는 것이 아니라 하위 노드로 한번 들어갈 때마다

남은 노드는 절반씩 줄어들테니까요.

O (n²)

위 그래프에서 오렌지색 점선 화살표에 해당 되는 부분입니다.

O(n²)는 자료의 크기가 커지면 커질 수록 복잡도가 급격하게 상승하므로 비효율적인 알고리즘이라고

판단하고 다른 대안을 찾거나 최대한 알고리즘 특성을 고려하여 입력 데이터를 최적화 해야 하겠죠.

대표적인 예로 이중 for문을 들 수 있겠습니다.

여기까지! 오늘은 주로 자주 사용 되는 함수들 위주로 살펴 보았습니다.

여기서 살펴본 함수들 외에도 O (nlog₂n), O (n³), O (2ⁿ), O (n!) 등의 함수가 있으니 궁금하신 분들은

구글에서 Big-O notation이나 Big-O Complexity로 검색해보시면 도움이 되실 거라고 믿습니다.

중요한건 위와 같은 그래프에서 수직 성분에 해당하는 알고리즘 복잡도가 하늘로 뻗쳐 올라갈수록 비효율적이다.

이것만 제대로 이해하면 되고, Big-O 표기법이나 세부 내용에 대해 달달 외울 필요는 없을 것 같아요.

O (1) > O (log₂n) > O (n) > O (nlog₂n) > O (n²)  > O (n³) > O (2ⁿ) > O (n!)

바로 이게 오늘의 키포인트 인 것 같네요. 대충 이 정도만 기억하고 있다가 비효율 적이다 아니다만

판단할 수 있다면 Big-O 표기법은 더 파지 않아도 되는 걸로 결론을 내고 마무리 짓겠습니다.

그 외에 더 알고 싶은 점이나 의문이 생기는 부분들 댓글로 남겨드리면 최대한 도움을 드려볼께요.

공감(♥) 및 댓글은 글쓴이에게 커다란 힘이 됩니다.

길지 않은 이 글을 쓰는데 나름 몇 시간이 걸렸어요^^;

저에게 1초만 시간을 내주셔서 공감 버튼 꾸욱 눌러주세요^^

제 블로그를 방문해 주신 모든 분들 사랑합니다^^

이상입니다. 감사합니다!