빅오(Big-O) 표기법과 시간 복잡도의 의미와 필요성

안녕하세요. Readerr입니다.

 

자료구조, 알고리즘 등 많은 부분에서 반드시 알아야 할 것이, "그래서 시간 복잡도는 얼마인가?"입니다.

면접에서 어떤 자료구조의 시간 복잡도는 어떻게 되는지 물어보는 경우도 많고, 알고리즘 문제를 풀 때도 특정 시간 복잡도 내에 풀어야 하는 경우가 많죠.

 

그렇다면 이 '시간 복잡도'가 무엇이냐.

말 그대로 "특정 작업을 하는데에 얼마만큼 시간이 걸리느냐"입니다. 그러나 일반적으로 '몇 회의 작업을 하느냐'라는 의미로 보는 것이 더 쉽겠네요.

 

빅오 표기법

시간 복잡도에 사용되는 대표적인 개념은 바로 빅오(Big-O) 표기법이에요.

어렵게 생각하실 거 없이, 변수들 중 최고차항만 계산하겠다는 겁니다.

예를 들어 'x² * 2x * 3'이라는 계산식이 있다고 가정했을 때, 이를 빅오 표기법으로 계산하자면 O(x²)이 되는거에요. x²이 최고차항이니까.

그렇다면 다른 값들은 생각보다 값이 클 수 있는데 왜 무시하느냐 생각이 들 수 있을 텐데, 대입을 한번 해볼게요.

x = 100을 대입해봅시다.

x² = 10000

2x = 200

위와 같은 값이 나타나게 돼요. 이러면 x²에 비해 2x가 아주 귀여운 값이 됐죠?

만약에 2x가 아니라 100x가 된다면 x²과 값이 같게 되기는 하겠지만, 일반적으로 상수값은 변수값과 그 차항에 비해 무시해도 될 만한 숫자이기 때문에 빅오 표기법에서는 모든 상수값을 무시합니다.

 

다음으로는 실제로 빅오 표기법으로 시간 복잡도를 도출해볼게요.

우선, 시간 복잡도를 이해할 수 있도록 간단한 코드인 구구단을 보면서 이해해 보시죠.

public class Main {
    public static void main(String[] args) {
        // 2단~9단까지의 구구단
        for (int i = 2; i <= 9; i++) {
            System.out.println("==============" + i + "단==============");
            for (int j = 1; j <= 9; j++) {
                System.out.println(i + " X " + j + " = " + (i * j));
            }
        }
    }
}

시간 복잡도를 계산할 때, 작업량은 '한 사이클' 기준입니다.

한 사이클이란 한 번의 계산으로 끝나는 것이 아니라, 반복문 등 여러 번의 작업이 요구되는 기준입니다.

예를 들어, 위 코드의 System.out.println(i + " X " + j + " = " + (i * j)); 의 경우, 단순 계산 및 출력으로 한 번의 계산으로 끝나게 되죠. 그런데 반복문 같은 경우에는 한 번이 아니라 여러 번에 걸쳐 작업을 하게 됩니다.

 

시간 복잡도에서 중요한 것은 바로 이 사이클입니다. 참고로 사이클이라고 하는 것은 도움을 돕기 위해 제가 임의로 만들어 낸 말이니, 참고만 부탁드립니다.

그럼, 구구단의 총 작업 횟수를 세볼게요. 정확하게 하고자 한다면 세야 할 내용이지만, 대략적인 시간 복잡도 산출을 위해서는 단순 계산 및 출력문은 따로 세지 않아도 된다고 말씀드렸으니, 총 작업량은 첫 번째 반복문에서 i에 2~9까지 대입하여 총 8회, 두 번째 반복문에서 j에 1~9까지 대입하여 총 9회. 즉, 8 * 9 = 72로 가정합니다.

그렇다면, 이 반복되는 숫자들을 변수 n으로 치환해봅시다. 8과 9는 값의 차이가 크게 나지 않으니 둘 다 똑같이 n 변수로 가정할게요. 그렇다면 '8 * 9 = 72 => n * n = n²'입니다.

즉, 이 구구단은 O(n²)의 시간 복잡도를 가진 알고리즘이에요.

 

그럼, 다음 코드를 볼게요. 이 내용은 헷갈릴 수 있는 부분이기 때문에 중요합니다.

public class Main {
    public static void main(String[] args) {
        // 2단~9단까지의 구구단
        for (int i = 2; i <= 9; i++) {
            System.out.println("==============" + i + "단==============");
            for (int j = 1; j <= 9; j++) {
                System.out.println(i + " X " + j + " = " + (i * j));
            }

            for (int j = 10; j <= 19; j++) {
                System.out.println(i + " X " + j + " = " + (i * j));
            }
        }
    }
}

구구단을 단순히 * 9까지만 하는 것이 아니라, * 19까지 계산하는 로직으로 변경을 했어요.

그럼 이 코드의 시간 복잡도는 얼마일까요?

 

의아하게도 이전과 마찬가지로 n²입니다.

제가 이전에 'x² * 2x * 3'으로 예시를 드렸었고, 빅오 표기법에서는 x²만 표시된다고 말씀드렸었죠.

위 구구단을 수식으로 나타내자면, 'n² * (n + n)' => 'n² * 2n'이에요. 즉, 최고차항인 n²만 살아남는 거죠.

 

빅오 표기법에서는 무조건 최고차항만 보시면 됩니다.

 

시간 복잡도

빅오 표기법과 도출 방법은 이 정도로 마치고, 시간 복잡도에 대해서 설명해볼게요.

시간 복잡도는 빅오 표기법에서 도출되는 값이라고 보시면 됩니다.

그리고 알아야 할 사항으로, 일반적으로 알고리즘 테스트를 볼 때 총 작업량이 1억(100,000,000)번을 넘으면 시간 복잡도 면에서 탈락합니다. 예를 들면, n = 100,000이라고 가정한다면, n²으로 풀면 시간 복잡도를 통과를 못한다는 거죠.

 

시간 복잡도에서 흔히 갖게 되는 값과 그 크기를 비교해볼게요.

 

O(N!) > O(2^n) > O(N²) > O(N log N) > O(N) > O(Log N) > O(1)

 

먼저 저 값들이 무엇인지 모르실 수도 있으니 설명을 드려볼게요.O(N!)에서 '!'는 팩토리얼을 의미하며, 예를 들어 '5! = 5 * 4 * 3 * 2 * 1'과 같은 값을 갖게 되는 것이 팩토리얼입니다.

 

O(2^n)에서 ^ 특수문자 뒤에 오는 숫자는 제곱되는 값을 말합니다. 즉, O(2^2) = O(2²)이죠.

 

O(Log N)은 한 번 실행할 때마다 횟수가 절반으로 줄어드는 것을 의미합니다. 예를 들어 다음과 같은 코드가 있다고 가정할게요. Log N은 이전에 수학 배우실 때 기억을 갖고 계신 분도 많을 테니, 무엇을 의미하는지 아시는 분은 넘어가도 됩니다. 또는 결론만 보셔도 돼요.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int find = 2;
        int count = 1;
        int i = 0;
        int l = 0;
        int r = arr.length - 1;

        // 배열에서 1~10까지의 수 중, 변수 find에 들어가 있는 값 2를 찾는 알고리즘
        while (true) {
            i = (l + r) / 2;
            if (find == arr[i]) {
                System.out.println(count + "번만에 찾았습니다.");
                break;
            }

            if (l > r) {
                System.out.println(count + "번을 탐색해도 해당 값을 찾지 못했습니다.");
                break;
            }

            if (find > arr[i]) {
                l = i + 1;
            } else {
                r = i - 1;
            }
            count++;
        }
    }
}

위 코드는 이진 탐색에서 사용되는 방법인데, 지금 이해 안 되셔도 괜찮아요.

대충 설명을 드리자면, 1부터 10까지 저장된 배열이 있고, 2라는 값을 찾고 싶은 경우에 다음과 같이 탐색합니다.

1. 찾는 값과 배열 중간에 있는 값을 비교한다.

2. 두 값이 다른 경우, 찾는 값이 중간 값보다 작은 경우에는 중간값 기준 배열의 왼쪽을 확인하고, 큰 경우에는 배열의 오른쪽을 확인한다.

3. 이를 값을 찾을 때까지 반복한다.

 

작성한 코드로 설명드려보자면,

1. 찾는 값 = 2, 중간 값 = 6

2. 2는 6보다 작으므로, 1~5까지의 배열 중에서 가운데에 있는 값을 다시 확인

3. 찾는 값 = 2, 중간 값 = 3

4. 2는 3보다 작으므로, 1~2까지의 배열 중에서 가운데에 있는 값 확인

5. 찾는 값 = 2, 중간 값 = 2

6. 찾는 값과 중간 값이 같으므로, 몇 번의 작업이 걸렸는지 반환

 

위 방법대로 짜여진 코드인데, 코드를 당장 이해하는 것보다 중요한 점은 '한 번 작업을 할 때마다 확인할 것이 절반씩 줄었다'입니다.

원래 1~10까지 담긴 배열 전체를 조회하려면 10번을 해야 하는데, 3번의 작업만으로 값을 찾을 수 있었고, 이와 같이 한 번 작업할 때마다 확인할 경우의 수가 절반씩 줄어드는 알고리즘을 O(Log N)의 시간 복잡도를 갖고 있다고 합니다.

 

다시 본론으로 돌아와서, 프로그래머는 가능한 적은 시간 복잡도를 가질 수 있도록 알고리즘을 구현해야 하며, 조금 난이도가 있는 알고리즘 문제에서는 이 시간 복잡도를 최소로 갖는 알고리즘을 구현하는 문제를 내고 있으니, 어떤 알고리즘을 보면 시간 복잡도를 계산하는 습관을 들이셔야 합니다.

 

학습에 도움이 되셨기를 바랍니다.