알고리즘 Featured

[알고리즘 기초] 복잡도 - 시간 복잡도와 공간 복잡도, Big-O 표기법

시간복잡도는 “입력 크기 n이 커질 때 실행 시간이 얼마나 늘어나는가”, 공간복잡도는 “추가 메모리를 얼마나 쓰는가”를 점근적으로 평가한다. 상수/하드웨어/캐시의 영향은 실무에서 크지만, 알고리즘 비교의 1차 기준은 여전히 Big-O다.

Gibeom Kim

21 Sep 2025 • 8 min read

Photo by Markus Spiske / Unsplash

복잡도란?

복잡도란 알고리즘이 얼마나 효울적인지를 평가하는 기준이다. 크게 두 가지로 나뉘어진다.

시간 복잡도 (time complexity) : 입력 크기 n이 커질 때, 알고리즘이 실행되는 데 걸리는 시간이 얼마나 늘어나는지 나타내는 지표
공간 복잡도 (space complexity) : 알고리즘이 실행될 때 추가로 필요한 메모리의 양

복잡도 표기법

입력 크기 n이 커질 때 성능이 어떤 차수로 변하는지를 비교하기 위해 도입한 표기법으로, 상수나 구현 세부를 걷어내고 비교한다. 시간 복잡도와 공간 복잡도에 동일하게 사용된다.

Big-O (상한): 최악/상한을 나타내는 지표. “이보다 나쁘지 않다.”
Θ (세타, 동치): 상한/하한이 같은 정확한 차수.
Ω (오메가, 하한): 최선/하한을 나타내는 지표. “이보다 좋지 않다.”

실무나 코딩테스트 등에서는 Big O 표기법 정도만 이해해도 충분하다.

Big-O 표기법

알고리즘의 성능 상한(Upper Bound)을 나타내는 수학적 기호이다. 즉, 입력 크기 n이 무한이 커질 때, 최악의 경우 실행 시간(또는 메모리 사용량)이 얼마나 빠르게 증가할 수 있는가를 표현한 것이다.

공식 정의는 다음과 같다:

$$ f(n) = O(g(n)) \;\;\iff\;\; \exists c > 0, n_0 \;\; \text{s.t.} \;\; \forall n \ge n_0,\; f(n) \le c \cdot g(n) $$

사실 정의만 보면 직관적으로 이해하기 쉽지 않는데, 쉽게 말하면 f(n)이 g(n)보다 커지지 않는다는 뜻이다. 직관적으로는 다항식에서 가장 빠르게 증가하는 최고차항만 고르면 된다고 생각하면 이해하기 쉽다.

예를 들어 다음과 같이 표현할 수 있다.

$$ 3n^2 + 2n + 7 = O(n^2) $$

복잡도 증가 순서

$$ O(1) \;<\; O(\log n) \;<\; O(n) \;<\; O(n \log n) \;<\; O(n^2) \;<\; O(2^n) \;<\; O(n!) $$

시간 복잡도에서의 Big-O

입력 크기 n이 커질 때 실행 시간이 얼마나 빠르게 증가하는지에 대한 상한(최악)을 나타내는 지표이다.

자주 쓰이는 예

Big-O	의미	예시 알고리즘
$O(1)$	상수 시간	배열 인덱스 접근 `arr[i]`
$O(\log n)$	로그 시간	이진 탐색
$O(n)$	선형 시간	배열 전체 순회
$O(n \log n)$	준선형	병합 정렬, `std::sort`
$O(n^2)$	제곱 시간	이중 루프(버블정렬)
$O(2^n)$	지수 시간	부분집합 탐색(브루트포스)
$O(n!)$	팩토리얼 시간	순열 완전 탐색

루프 1회: O(n)

for (int i = 0; i < n; i++) { ... } // O(n)

루프 1회

N회 중첩 루프: 다항 시간 O(n^N)

for (int i = 0; i < n; i++) 
{
    for (int j = 0; j < n; j++) { ... } // O(n^2)
}

루프 2회일 시

STL에서 시간 복잡도

항목	평균/보장 복잡도 (대략)
`std::vector` 인덱스	$O(1)$
`vector::push_back`	평균비용 $O(1)$ (가끔 재할당은 $O(n)$ )
`vector` 중간 `insert/erase`	$O(n)$ 이동
`std::array` 인덱스	$O(1)$
`std::list` 특정 위치 삽입/삭제	$O(1)$ (이터레이터 이미 알 때)
`std::map`(RB-tree) 찾기/삽입/삭제	$O(\log n)$
`std::unordered_map` 찾기/삽입/삭제제	평균 $O(1)$ , 최악 $O(n)$
`std::priority_queue` push/pop	$O(\log n)$
`std::sort`	평균 $O(n\log n)$

예제

#include <vector>
#include <algorithm>

// 선형탐색 - O(n)
bool containsLinear(const std::vector<int> &arr, int target)
{
    for (int v : arr)
    {
        if (v == target)
        {
            return true;
        }
    }
    return false;
}

// 이진 탐색 - O(logn)
bool containsBinary(const std::vector<int> &arr, int target)
{
    return std::binary_search(arr.begin(), arr.end(), target);
}

// 이중 루프(삼각형의 합) - O(n^2)
int countPairsLE(const std::vector<int> &a, int limit)
{
    int cnt = 0;
    for (int i = 0; i < static_cast<int>(a.size()); i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (a[i] + a[j] <= limit)
            {
                ++cnt;
            }
        }
    }
    return cnt; // 실행 횟수 ~ 1 + 2 + ... + n = O(n^2)
}


// k 번째 큰 원소 - 평균 O(n)
int kthLargest(std::vector<int> a, int k)
{
    std::nth_element(a.begin(), a.end() - k, a.end());
    return *(a.end() - k);
}

공간 복잡도에서의 Big-O

알고리즘이 실행될 때 필요한 메모리의 크기를 입력 N의 함수로 나타내는 지표이다. 입력 데이터를 저장하는 데 필요한 공간뿐만 아니라, 알고리즘 수행 중 추가로 할당되는 변수, 배열, 재귀 호출 스택까지 포함한다

구성 요소

고정 공간 (Fixed Part)
- 코드, 상수, 전역 변수, 함수 등 프로그램 실행과 무관하게 항상 필요한 공간
- 입력 크기와 무관하게 O(1)
가변 공간 (Variable Part)
- 입력 크기와 함께 변하는 공간
- 지역 변수, 동적 할당 배열, 재귀 호출 스택 등

예제

// 단순 합계 계산
long long sum(const std::vector<int> &arr)
{
    long long acc = 0;
    for (int v : arr)
    {
        acc += v;
    }
    return acc;
}

단순 합계 계산하는 코드

시간 복잡도: O(n)
공간 복잡도: O(1) (입력 외 추가 변수 acc 하나뿐)

// 보조배열 사용
std::vector<int> copyAndDouble(const std::vector<int> &arr)
{
    std::vector<int> result;
    result.reserve(arr.size());
    for (int v : arr)
    {
        result.push_back(v * 2);
    }
    return result;
}

복사 후 2를 곱해서 새로운 배열을 만드는 경우

시간 복잡도: O(n)
공간 복잡도: O(n) (새로운 배열 result 필요)

//재귀 깊이
int factorial(int n)
{
    if (n == 0) 
    {
      return 1;
    }
    return n * factorial(n - 1);
}

재귀함수 펙토리얼

시간 복잡도: O(n)
공간 복잡도: O(n) (재귀 스택 프레임 n개)

// 동적 계획법 (DP 테이블)
int fibDP(int n)
{
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

DP 테이블

시간 복잡도: O(n)
공간 복잡도: O(n) (dp 배열 크기 n+1)

복잡도 이론의 현재적 의미

알고리즘 복잡도 이론은 1960~70년대에 본격적으로 적립이 되었는데, 이 당시에는 하드웨어 성능이 매우 제한적이었다. 따라서 입력 크기에 따른 실행 시간과 메모리 사용량을 추상적으로 예측할 수 있는 도루고서 복잡도 분석이 매우 중요한 위치를 차지했었다.

그러나 현대에 와서는 상황이 많이 달라졌다. 일반적인 PC와 서버에서는 과거와 비교할 수 없을 정도로 높은 성능을 갖추고 있기 때문에 일반적인 애플리케이션 개발에 있어서는 복잡도 보다는 코드 가독성, 유지보수성, 라이브러리 재활용성을 더 중요하시하는 경우가 많다.

그렇다 하더라도 복잡도 이론이 의미를 잃어버린 것은 아니다. 특정 영역에서는 여전히 핵심적인 기준으로 삼고 있다:

임베디드 / IoT 장비: 초저용량 메모리, 수 MHz짜리 장비 등
대규모 데이터 처리: 수백만 ~ 수억 단위의 데이터가 오가는 시스템
온라인 서비스: 결제 서버, 게임 서버 등
실시간 안전 필수 시스템: 자동차, 항공, 의료 등 최악의 시간이 중요한 경

예제

시간 복잡도 관련 프로그래머스 문제와 각 방식 별 실행 결과는 아래 포스팅 참고해주시기 바랍니다 😄