샷건치며 배우는 자료구조 with C++, 2화

시간 복잡도에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

C 언어 구현 내용 제거
- 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

시간 복잡도

시간 복잡도는 코딩 테스트에서나 다룰 내용이지만... 이 자료구조 글에서 언급하는 이유는 각 자료구조의 성능을 알기 위해서 입니다. 각 자료구조마다 데이터를 추가, 삭제, 탐색하는 방식이 다르기 때문에 연산 속도에서 차이를 보입니다. 어떤 자료구조를 선택해야 할지 판단하려면 이 시간 복잡도 개념을 알아야 합니다. 수학적인 개념이 포함되기 때문에 다소 어려울 수 있습니다만, 최대한 쉽게 풀어서 설명하겠습니다. 참고로 저 수포자입니다.

시간 복잡도^{Time Complexity}는 알고리즘의 성능을 나타내는 지표라 할 수 있습니다. 정확히는 입력의 크기 \(N\)이 증가할 때 알고리즘의 수행 시간이 어떻게 변하는 지를 나타냅니다. 정확한 실행 시간을 나타내는 것이 아닌 속도의 증가 패턴을 표현하는 것입니다.

표기법	설명
빅-오(Big-O, 𝑂)	입력의 크기가 커질 때 수행 시간의 상한^{Upper Bound}을 나타냅니다. 주로 최악의 경우(Worst Case)를 기준으로 합니다.
빅-오메가(Omega, Ω)	입력의 크기가 커질 때 수행 시간의 하한^{Lower Bound}을 나타냅니다. 최선의 경우(Best Case)라도 이보다 빠를 수 없음을 나타냅니다.
빅-세타(Theta, Θ)	상한과 하한이 동일할 때 평균적인 경우(Average Case)를 나타냅니다.

알고리즘의 수행 시간을 분석 및 표기할 때 빅-오, 빅-오메가, 빅-세타를 사용하는 데 그중 빅-오가 가장 널리 사용됩니다. 왜냐하면 빅-오는 최악의 경우를 다루기 때문에 최악의 상황에서 이 알고리즘이 얼마나 수행되는가?를 확인할 수 있기 때문입니다. 그래서 효율적인 알고리즘을 선택하는 데 있어 큰 도움을 줍니다.

빅-오 표기법을 주로 사용하기 때문에 빅-오 표기법에 대한 설명만 자세히하고 나머지는 간략하게 작성합니다.

빅-오(Big-O, 𝑂) 표기

빅-오 표기법은 알고리즘이 입력 크기(데이터)가 증가할 때 실행 시간이 어떻게 변하는지 알려주는 표기법입니다. 정확한 실행 시간을 측정하는 것이 아니라... 입력 크기에 따른 실행 시간의 증가 패턴을 보여줍니다.

어떤 작업을 1초 만에 처리할 수 있다고 가정해봅시다. 그런데 이 데이터가 100배 또는 1,000배 늘어나면 실행 시간은 어떻게 변할까요? 여전히 1초 만에 후딱 처리할까요? 아니면 늘어난 데이터의 수만큼 더 걸릴까요?

빅-오 표기법은 위 질문에 대한 답을 제시해줍니다.

상한

빅-오 표기법에서 상한이라는 단어가 무조건 언급됩니다. 음식이 상했다는 그 뜻이 아니라... 상한^{Upper Bound}은 알고리즘이 아무리 느려져도 이 선은 넘지 않겠다는... 최악이어도 이정도까지 걸린다는 한계선을 나타냅니다.(1) 예를 들어, 상한이 \(O(n)\)이라면 시간이 \(n\)보다 더 늘어나지 않는다는 겁니다.

그래 그거면 된거야...

대표적인 표기법

빅-오 표기법	설명
\(O(1)\)	상수 시간
\(O(log n)\)	로그 시간
\(O(n)\)	선형 시간
\(O(n log n)\)	선형 로그 시간
\(O(n^2)\)	이차 시간
\(O(2^n)\)	지수 시간

\(O(1)\)

데이터의 양이 얼마나 많든 실행 시간이 항상 일정합니다. 입력 크기(데이터)와 상관없이 동일한 시간이 걸리는 가장 효율적인 경우입니다.

대표적인 예로 배열의 인덱스입니다. 배열의 특정 요소에 접근하는 인덱스 연산은 배열의 크기와는 상관없이 바로 접근할 수 있기 때문에 매우 빠른 속도를 보입니다.
\(O(log n)\)

데이터가 클 수록 실행 시간은 아주 천천히 늘어납니다.

예를 들어, 식당에서 손님들이 번호가 매겨진 테이블에서 주문을 한다고 가정해봅시다. 이 식당은 손님들이 앉은 순서가 아닌 번호를 기준으로 한다고 해봅시다. 번호를 더 빠르게 찾기 위해 이진 탐색 방식으로 처리한다고 가정해봅시다. 100명의 손님이 대기 중이라면 이를 절반씩 나누어 찾는 방식으로, 대기 시간이 엄청나게 줄어듭니다. \(O(n)\)과는 다르게 손님의 수가 늘어도 그만큼 증가하지 않고 로그 시간 비율로 늘어나죠.
ㅅㅂ! 로그만큼 증가한다는 게 뭐죠?

로그^log는 어떤 숫자를 만들기 위해 몇 번 곱해야하는 지를 묻는 개념입니다. 음... 더 자세히 설명하려면 이 한 페이지를 다 써야하기 때문에 생략하구요...

컴퓨터 과학(+ 프로그래밍)에서 log n은 밑(1)이 2인 로그, 즉 \(log_2 n\)을 의미합니다. 왜냐하면 이진법을 기반으로 동작하기 때문입니다. 그리고 빅-오 표기법에서 밑이 생략된 이유는 아래에서 자세히 설명하겠지만 굳이 중요하지 않기 때문입니다.
1. 밑^Base은 특정 숫자를 얻기 위해 몇 번 거듭제곱해야 하는 지를 나타냅니다. 말 그대로 이 밑을 기반으로 합니다.
\(log_2(8)\)은 3이라는 결괏값을 나타냅니다. 왜냐하면 2를 3번 곱해야 8이되니까 그렇습니다. 좀 더 쉽게 설명하자면 N을 2로 얼마나 나누어야 1이 될까 정도로 생각하시면 되겠습니다.

정리하자면... 로그만큼 증가한다는 건 입력 크기에 비례하지 않고 조금씩 늘어난다는 걸 의미합니다. 생각보다 조금씩.

\(log_2(8)\) = 3, \(log_2(16)\) = 4, \(log_2(1024)\) = 10 등 N이 아무리 커도 시간은 존나 조금 늘어나는 걸 볼 수 있습니다. 로그만큼 증가한다는 건 이 뜻입니다. N이 아무리 기하급수적으로 커져도 시간은 천천히 늘어납니다. ~~내 나이도 그랬으면...~~
\(O(n)\)

데이터의 양에 비례하여 실행 시간이 증가합니다. 데이터가 2배로 커지면 실행 시간도 2배, 10배라면 10배가 됩니다.

예를 들어, 식당에서 손님의 주문을 받는 데 1분이 걸린다고 해봅시다. 1명이라면 1분이면 끝나지만 10명이라면 10분, 100명이라면 100분이 걸립니다.
\(O(n log n)\)

선형 시간과 로그 시간의 결합으로, 입력 크기에 비례하지만 그 증가율은 선형 시간보다는 느리고 로그 시간보다는 빠름을 나타냅니다.
\(O(n^2)\)

데이터의 양이 증가할 수록 실행 시간이 제곱에 비례하여 급격하게 늘어납니다. 데이터가 두 배로 커지면 시간은 네 배가 되버립니다;; 데이터가 많아질 수록 매우 비효율적이라 가급적 피해야 합니다.
\(O(2^n)\)

데이터의 양이 증가할 수록 실행 시간이 기하급수적으로 늘어납니다. 데이터가 아주 조금 커져도 실행 시간이 엄청나게 증가합니다. 진짜 존나 비효율적이라 이차 시간과 함께 가장 피해야하는 경우입니다.

계수와 상수를 무시한다

빅-오 표기법은 다항식에서 최고차항만 남기고 계수와 상수를 지우고 무시합니다.

항, 차수, 최고차항, 계수

다항식^Polynomial은 변수와 상수들의 합, 차, 곱으로 이루어진 식입니다.
항^Term은 \(ax^n\), \(bx\), \(c\)와 같은 구성 요소를 말합니다.
차수^Degree는 다항식에서 가장 높은 차수를 가진 항의 차수가 다항식의 차수가 되고, 다항식의 변수를 거듭제곱한 지수가 차수입니다.
계수^Coefficient는 각 항에 곱하는 상수입니다. 위 N차 다항식에서 \(a\), \(b\), \(c\)가 계수가 됩니다.
최고차항^{Highest Term}은 다항식에서 가장 차수가 높은 항입니다. 위 예시는 최고차항이 N차항이라 N차 다항식이라 부릅니다.

빅-오 표기법에서 최고차항만 남기고 계수와 상수를 지우는 이유는 알고리즘의 실행 시간을 표현하는 함수에서 가장 큰 영향을 미치는 부분만 남기고 나머지를 단순화하기(미치는 영향이 적기 때문) 때문입니다. 애초에 정확한 값이 아니라 어느정도인가를 파악하는 것이 목적입니다.

예를 들어, 어떤 알고리즘의 실행 시간이 \(T(n) = 3n^2 + 2n + 1\)이라고 가정해봅시다. \(T(n)\)은 입력 크기가 \(n\)일 때 실행 시간을 의미합니다.

위 다항식에서 최고차항은 \(n\)의 차수가 가장 높은 항입니다. 즉, \(3n^2\)가 최고차항이 됩니다. \(n\)이 커질수록 \(n^2\)가 실행 시간에 가장 큰 영향을 미치기 때문이죠. 나머지 항은 \(n\)이 커져도 \(3n^2\)에 비해 상대적으로 영향이 작습니다.

최고차항 \(3n^2\)에서 계수 \(3\)을 지워버립니다. 왜냐하면 \(n\)이 커지면 계수가 성능에 미치는 영향이 그리 크지 않습니다. \(3n^2\)이나 \(5n^2\)이나 증가율 자체는 비슷하기 때문입니다.

마지막으로 나머지 낮은 차수와 상수항을 무시합니다. 최종적으로 \(T(n) = 3n^2 + 2n + 1 = O(n^2)\)이 됩니다. 최종적으로 알고리즘의 실행 시간은 \(O(n^2)\)임을 알 수 있습니다.

빅-오메가(Omega, Ω) 표기

빅-오메가 표기법은 알고리즘의 실행 시간의 하한^{Lower Bound}을 나타냅니다. 이는 특정 상황에서 알고리즘이 이보다 더 빨라지거나 적은 자원을 사용할 수 없다는 걸 의미합니다. 즉, 아무리 잘해도 넌 거기까지야!라는 겁니다. 아무리 잘해도 이 시간은 걸린다라는 말입니다. 아무리 노력해도 재능은 못따라 잡는 것처럼 말이죠.

빅-세타(Theta, Θ) 표기

빅-세타 표기법은 상한과 하한이 동일한 범위에 있을 경우에나 사용되며, 알고리즘의 실행 시간이 정확히 맞아 떨어질 때를 나타냅니다. 이는 최선, 최악, 평균 케이스 모두 적용될 수 있습니다. 만약, 상한과 하한이 다르다면 빅-세타 표기법을 사용할 수 없고... 빅-오와 빅-오메가를 따로 표기해야 합니다.

간단하게 말하자면 상한과 하한이 동일한 경우를 나타내기 때문에 알고리즘이 평균적으로 수행되는 시간을 나타냅니다.

정리

게시글을 읽으면서 빅-오는 최악, 빅-오메가는 최선, 빅-세타는 평균 케이스에만 해당한다고 오해하기 쉽습니다. 하지만 이 표기법들은 최악, 최선, 평균 케이스 모두에 적용될 수 있습니다. 특정 케이스에 얽매이지 않습니다.

예를 들어, 퀵 정렬의 평균 시간 복잡도는 \(Θ(n log n)\)로 알려져 있습니다. 최악의 케이스는 \(O(n^2)\)(하한도 마찬가지), 최선의 케이스는 \(Ω(n log n)\)(상한도 마찬가지)로 나타나기도 합니다. 그럼에도 \(Θ(n log n)\)로 알려진 이유는 평균적인 경우에서 상한과 하한이 거의 비슷하기 때문입니다. 퀵 정렬은 피벗을 기준으로 분할하는 알고리즘입니다. 피벗을 잘 선택하면 빨리 분할이 이루어지고, 운빨ㅈ망 수준으로 뽑으면 성능이 나빠집니다. 만약 피벗을 무작위로 선택한다고 하면 좋은 피벗과 안 좋은 피벗이 나올 수 있습니다. 이렇게 여러 번 실행한 결과를 평균적으로 보면 성능이 꼭 최악이나 최선에 치우치지 않고 보통의 경우로 나옵니다. 즉, 평균적인 경우에는 상한과 하한이 비슷한 \(n log n\)에 수렴하기 때문에 퀵 정렬의 평균 시간 복잡도는 \(O(n log n)\) 또는 \(Θ(n log n)\)으로 나타낼 수 있습니다.

최악과 최선이 달라 빅-세타를 증명하지 못해도 빅-오와 빅-오메가를 따로 표기하여 알고리즘의 시간 복잡도를 각각 상한과 하한으로 분석할 수도 있습니다.

연습문제 1

practice_1.c
#include <stdio.h>

int main(int argc, char* argv[]) {
    int target = 10;
    int arr[20] = { 2, 6, 3, 9, 7, 9, 23, 20, 78, 1, 8, 3, 65, 3, 6, 889, 0, 7, 9, 4 };

    for (int i = 0; i < 20; ++i) {
        if (arr[i] == target) {
            break;
        }
    }

    return 0;
}

배열 arr에서 target의 값을 찾기 위한 탐색 과정입니다. 위 코드의 상한과 하한을 구해보세요.

해답

상한

빅-오는 최악의 경우를 기준으로 상한을 분석합니다. 위 코드에서 최악의 경우는 target이 배열에 없거나 배열의 가장 끝에 있을 때입니다. 즉, 배열에 모든 요소를 확인해야 하는 거죠.

배열의 크기(\(N\))만큼 실행해야 하기 때문에 시간 복잡도는 \(O(n)\)입니다.
하한

빅-오메가는 최선의 경우를 기준으로 하한을 분석합니다. 위 코드에서 최선의 경우는 target이 배열의 첫 번째 요소로 있어 바로 찾았을 때입니다. 즉, 1번만 비교하면 됩니다.

단 1번의 비교로 끝나기 때문에 이보다 빠를 수 없습니다. 시간 복잡도는 \(Ω(1)\)입니다.

상한과 하한이 다르기 때문에 빅-세타 표기법으로 나타낼 수 없지만, target이 배열에 무조건 있다고 가정한다면 배열의 처음, 끝, 중간 어디에 있을 지 알 수 없기 때문에 평균적으로 배열의 절반 정도를 탐색하게 됩니다. 즉, 평균적으로 \(n/2\)번의 비교가 이루어집니다. \(O(n/2)\)로 나타내야 겠지만... 빅-오 표기법에서 상수는 무시하기 때문에 상수 \(\frac{1}{2}\)은 제거됩니다. 평균 \(O(n)\)입니다.

연습문제 2

practice_2.c
#include <stdio.h>

#define N 5

int main(int argc, char* argv[]) {
    int arr[N][N] = {};

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            printf("%d ", arr[i][j]);
        }
    }

    return 0;
}

2차원 배열 arr에 있는 값을 중첩 반복문을 통해 출력하고 있습니다. 위 코드의 상한과 하한을 구해보세요.

해답

상한

빅-오는 최악의 경우를 기준으로 상한을 분석합니다. 위 코드에서 최악의 경우는 별도로 탈출하는 조건식이 없기 때문에 반복문이 끝까지 실행된다는 점입니다.

for (int i = 0; i < N; ++i)는 i가 0부터 N - 1까지..., 즉 N번 반복합니다.

for (int j = 0; j < N; ++j)는 j가 0부터 N - 1까지..., 즉 N번 반복합니다.

첫 번째 반복문이 N번 반복할 때마다 두 번째 반복문도 N번 반복합니다. 즉, \(n \times n\)번 반복하며, \(n^2\)번 반복된다는 걸 알 수 있습니다.

따라서 시간 복잡도는 \(O(n^2)\)입니다.
하한

빅-오메가는 최선의 경우를 기준으로 하한을 분석합니다. 위 코드는 별도로 탈출하는 조건식이 없기 때문에 반복문이 끝까지 실행된다는 점입니다.

시간 복잡도는 \(Ω(n^2)\)입니다.
빅-세타

상한과 하한이 같아 빅-세타 표기법으로 표현할 수 있습니다. \(Θ(n^2)\)

연습문제 3

practice_3.c
#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0, right = size - 1;

    while (left <= right) {
        // 중간 인덱스
        int mid = (left + right) / 2;

        // 타겟이 중앙에 있으면
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {     // 타겟이 중간값보다 크면 왼쪽 범위 버림
            left = mid + 1;
        } else {
            right = mid - 1;                // 타겟이 중간값보다 작으면 오른쪽 범위 버림
        }
    }

    return -1;
}

int main(int argc, char* argv[]) {
    int arr[] = { 1, 3, 5, 7, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int idx = binary_search(arr, size, target);

    return 0;
}

이진 탐색을 통해 정렬된 arr에서 target을 찾는 과정입니다. 상한과 하한을 구해보세요.

해답

상한

빅-오는 최악의 경우를 기준으로 상한을 분석합니다. 위 코드에서 최악의 경우는 target이 없거나 절반씩 계속 나누며 찾아야 할 때 입니다.

target의 값은 7로 되어 있습니다. 이를 찾는 과정은 아래와 같습니다.
1. mid의 값은 2입니다. arr[2]의 값 5와 비교합니다. target의 7이 더 크기 때문에 왼쪽의 범위를 버립니다.
2. mid의 값은 3입니다. arr[3]의 값 7과 비교합니다. target과 같기 때문에 반복문을 종료합니다.
최악의 경우에도 이진 탐색은 범위를 절반씩 줄여가기 때문에 최대 \(log_2(n)\)번 비교합니다.

따라서 시간 복잡도는 \(O(log n)\)입니다.

이진 탐색은 절반씩 줄이다가 1개가 남을 때까지 몇 번 나누는 지가 핵심입니다. 계속 나누다가 1이 될 때까지의 횟수가 \(log_2(n)\)의 특성입니다.
하한

빅-오메가는 최선의 경우를 기준으로 하한을 분석합니다. 위 코드에서 최선의 경우는 target이 중앙에 바로 있을 때입니다.

탐색하지 않기 때문에 시간 복잡도는 \(Ω(1)\)입니다. 이런 경우는 드물겠지만 이론적으로는 이렇습니다. 평균적으로는 \(log n\)입니다.