Big-O notation

[obzva]

들어가기 전에

2기 5주차 모임에서 시간 복잡도 분석을 하던 도중, 저와 다른 분들의 생각이 다른 순간이 있었습니다.

당시 디스코드 화상 채팅만으로 의견을 명확히 전달드리기 어려워서 차주에 제 생각을 정리하여 발표하기로 했습니다.

그런데 문득, Big O 표기에 대해 서로 다르게 이해하고 있다면 그것도 문제겠구나'라는 생각이 들었고 Big O 표기란 무엇인지 먼저 명확히 짚고 넘어가기로 하였습니다.

최대한 간단하게 전달하려다 보니까 엄밀한 내용에 대해서는 생략된 부분이 많습니다.

함께 이야기를 나누고픈 내용이 있다면 코멘트 부탁 드리겠습니다.

출처와 인용은 모두 'Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press'에서 가져왔습니다.

Big O notation

[수학적 정의]

Big O 표기는 특정 함수의 인자가 무한히 커진다고 가정했을 때, 해당 함수의 극한 성질을 설명하기 위해 도입된 개념입니다.

우리 개발자들, 알고리즘 문제 수련자들에게 좀 더 와닿는 표현으로 바꿔보면 다음과 같습니다.

input의 크기가 증가할 때, 실행 시간이나 사용 메모리 공간의 크기가 어떻게 증가하는지를 설명하기 위한 개념

실행 시간이 어떻게 증가하는가: Time Complexity (시간 복잡도)

사용 메모리 공간의 크기가 어떻게 증가하는가: Space Complexity (공간 복잡도)

알고리즘 문제 풀이를 할 때 우린 종종 Big O를 알고리즘을 실행하는 데에 걸리는 시간으로 생각하게 됩니다.

하지만 Big O로 설명하고자 하는 바는 어떻게 증가하는지이어야 합니다.

Big O notation 쉽게 구하기

알고리즘 분석에서 사용되는 Big O 표기를 쉽게 구하는 방법이 있습니다.

1. 증가율이 가장 큰 항만 남기고 모두 지운다.
2. 남은 항에서 상수 곱은 모두 지운다.

아래 예시에서 적용해보겠습니다.

간단한 예시

정수 n을 전달받는 함수 alg가 있다고 가정해보겠습니다.

function alg(int n) {
    for (int i = 0; i < n; ++i) {
        // do some calculation
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // do some calculation
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // do some calculation
        }
    }
}

alg 함수의 시간복잡도를 구해보겠습니다.

정수 n이 인자로 주어졌을 때, 함수 alg의 실행 시간을 f(n)이라고 합시다.

f(n) = n + 2 * n^2

f(n)에서 증가율이 가장 큰 항은 2 * n^2이므로 해당 항만 남깁니다.

n + 2 * n^2
-> 2 * n^2

2 * n^2 중에서 2는 n과 상관이 없는 상수이므로 해당 곱을 지웁니다.

2 * n^2
-> n^2

따라서 alg함수의 시간복잡도는 O(n^2)라고 표기할 수 있고, n이 증가함에 따라 실행 시간이 n^2와 비슷한 형태로 증가한다고 이해할 수 있습니다.

f(n) = n + 2 * n^2

let g(n) = n^2

for n_0 > 10 and c = 3, 0 <= f(n) <= 3 * g(n) for all n > n_0

therefore f(n) = O(g(n)) = O(n^2)

[DaleSeo]

@obzva 님, 유용한 자료 올려주셔서 감사합니다. Big O 복잡도 계산을 하는 방법을 예제와 함께 알려주시니 이해가 쉬운 것 같아요 👍