[알고리즘] 시간 복잡도(Time Complexity)란?

시간 복잡도 (Time Complexity)

코드 문제들을 풀거나 기능을 구현하면서 자신의 코드와 다른 사람들의 코드를 보면서

이런식으로 효율적으로 코드를 짤 수 있구나 ~ 하는 경험들이 한 번씩은 다 있었을 겁니다.

그렇게 남들이 효율적으로 잘 짠 코드를 보면 "어떻게 효율적으로 코드를 짤 수 있을까"라는 생각들을 할텐데요.

효율적인 코드를 짠 다는 것은 코드가 실행되는데 걸리는 시간에 대해 고민하는 것과 같습니다.

* 코드가 실행되는데 걸리는 시간 : 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는지?
* 효율적인 코드 : 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성

 

즉, 효율적인 알고리즘을 구현한다는 것은 시간의 비율을 최소화한 알고리즘을 구성한 것으로 "시간 복잡도"를 고민하는 것입니다.

이 시간 복잡도는 주로 Big-O 표기법을 사용해 나타냅니다.

---

Big-O 표기법

시간복잡도를 표기하는 방법

• Big-O (빅-오) : 최악의 시간을 고려
• Big-Ω (빅-오메가) : 최선의 시간을 고려
• Big-θ (빅-세타) : 중간(평균)의 시간을 고려

시간 복잡도를 표기하는 방법에는 위와 같이 3가지 방법이있습니다.

하지만 주로 Big-O 표기법을 사용하는데 그 이유는 아래와 같습니다.

Big-O 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간(만약의 상황)까지 고려할 수 있지만
Big-Ω 표기법은 최선의 경우가 만약 10초가 걸려야하는데 만약 20초가 걸린다면 최선의 경우를 고려했기 때문에 어떤 부분에서 문제가 발생 파악하는데 많은 시간이 걸립니다.
Big-θ 표기법도 마찬가지로 프로그램이 실행되는 평균의 시간이 30초인데 평균을 넘어 60초가 걸린다면 어떤 부분에서 문제가 발생했는지 파악하는데 많은 시간이 걸립니다.

 

---

Big-O 표기법의 종류

O(1) - 일정한 복잡도

입력값이 증가하더라도 시간이 늘어나지 않습니다.

즉, 입력값이 크기에 관계없이 즉시 출력값을 얻어 낼 수 있습니다.

상수의 시간 복잡도라는 의미도 가지고 있습니다.

    public static void O_1() {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};
        int index = 3;
        System.out.println(arr[index]); // 3
    }

 

O(n) - 선형 복잡도

입력값이 증가함에 따라 시간 또한 비례하여 증가합니다.

    public static void O_n(int n) {
        for (int i = 0; i < n; i++) {
            System.out.println(i); // n : 5 일때 => 01234
        }
    }

 

O(log n) - 로그 복잡도

Big-O 표기법 중 O(1)다음으로 빠른 시간 복잡도를 가집니다.

이진 트리 탐색 BST(Binary Search Tree) 알고리즘은 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어들어 이와 같은 시간 복잡도를 가집니다.

UP-Down 게임

만약 1 ~ 10 숫자 중에 제시자가 정한 하나의 숫자(7)를 맞춰야한다고 가정했을 때,
참가자가 4를 말했다면 제시자는 UP을 외치면서 5 ~ 10개의 숫자 중 하나를 말하면 됩니다.
여기서 참가자가 8을 말했다면 제시자는 Down을 외치면서 참가자는 5 ~ 7 숫자 중 하나의 숫자를 말하면됩니다.

이처럼 매번 숫자를 제시할 때마다 경우의 수가 절반으로 줄어드는 경우 O(log n)의 시간 복잡도를 가진 알고리즘이라고 할 수 있습니다.

 

O(n2) - 2차 복잡도

뒤에 숫자 2는 제곱이라는 뜻으로, 입력값이 증가함에 따라 시간이 n의 제곱만큼 증가하는 시간 복잡도 입니다.

 

입력값이 하나 일 때 1초가 걸린다면 아래의 이중 반복문의 경우 n의 값을 3을 주게 되면 3의 2제곱으로 9초가 걸리게 됩니다.

만약 3중 반복문 일 경우에는 3의 3제곱으로 27초가 걸리게 됩니다.

    public static void O_n2(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("i : " + i + " - j : " + j);
            }
        }
    }

 

O(2n) - 기하급수적 복잡도

Big-O 표기법 중 가장 느린 시간 복잡도로 입력값이 증가할 때마다 걸리는 시간은 2배씩 증가합니다.

대표적으로 피보나치 수열이 이와 같은 시간복잡도를 가집니다.

    public static int O_2n(int n) {
        if (n <= 1) {
            return 1;
        }
        // 피보나치 수열의 재귀적 호출
        return O_2n(n - 1) + O_2n(n - 2); // n이 5 일 때 => 8
    }