algo · 01

시간/공간 복잡도

알고리즘Big-O복잡도

시간/공간 복잡도(Big-O 표기법)는 입력 크기 n이 커질수록 실행 시간이나 메모리 사용량이 얼마나 빠르게 늘어나는지를 나타내는 표기법입니다. 정확한 초 단위가 아니라 "커지는 추세(패턴)"에 집중한다는 점이 핵심입니다.

핵심 개념

O(1) — 상수 시간

입력 크기와 상관없이 항상 일정한 횟수만 연산합니다. 예: 배열에서 인덱스로 값 하나를 바로 꺼내는 연산.

핵심 개념

O(log n) — 로그 시간

매 단계마다 처리할 범위를 절반씩 줄여나갈 때 나타납니다. 예: 다음 토픽에서 다룰 이진 탐색.

핵심 개념

O(n) — 선형 시간

입력 전체를 한 번씩은 훑어야 하는 경우입니다. 예: 배열을 처음부터 끝까지 순회하며 최댓값을 찾는 연산.

핵심 개념

O(n²) — 이차 시간

입력의 모든 쌍을 서로 비교해야 할 때 나타납니다. 예: 이중 for문, 버블 정렬(자료구조-09에서 다룸).

핵심 개념

O(2ⁿ) — 지수 시간

매 단계마다 선택지가 두 배씩 늘어날 때 나타납니다. 예: 캐시 없이 재귀로 계산하는 피보나치(자료구조-10에서 다룬 완전 탐색).

핵심 개념

시간·공간 트레이드오프

복잡도는 실행 시간뿐 아니라 메모리 사용량도 같은 방식(O(1), O(n)...)으로 표현합니다. 메모이제이션은 시간을 아끼는 대신 공간을 더 쓰는 대표적인 예입니다.

왜 정확한 초 단위가 아니라 빅오인가 — 컴퓨터 성능이나 사용하는 언어에 따라 실제 걸리는 시간은 달라지지만, "n이 커질 때 얼마나 빠르게 증가하는가"라는 패턴은 알고리즘 고유의 성질이라 비교 기준으로 삼기 좋습니다.

최선 / 평균 / 최악의 경우 — 같은 알고리즘도 입력에 따라 다르게 동작할 수 있습니다(예: 이미 정렬된 배열에서는 버블 정렬도 훨씬 빠르게 끝납니다). 빅오는 보통 가장 나쁜 경우(최악)를 기준으로 표기해 안전하게 성능을 예측합니다.

실전에서의 의미 — n이 10 정도면 어떤 알고리즘을 써도 체감 차이가 없습니다. 하지만 n이 수백만 단위로 커지면 O(n²) 알고리즘은 멈춘 것처럼 느껴지고, O(n log n)이나 O(n)은 여전히 빠릅니다. 그래서 문제 규모에 맞는 알고리즘 선택이 중요합니다.

이 시각화에서 확인할 것 — "그래프로 보기"에서는 n이 커질 때 다섯 복잡도가 그리는 곡선의 모양 차이를, "숫자로 비교"에서는 n=10 / 100 / 1000일 때 실제 연산 횟수가 얼마나 벌어지는지를 직접 숫자로 확인합니다.

빅오가 필요한 이유와 표기의 뜻

알고리즘을 비교할 때 실제 걸린 시간은 컴퓨터와 언어마다 달라서 기준이 되기 어렵습니다. 그래서 입력 크기 n에 대해 연산 횟수가 어떤 함수로 늘어나는지를 보는 점근 표기를 씁니다. 교재(CLRS)에서 O는 증가율의 상한, Ω는 하한, Θ는 같은 증가율로 위와 아래를 모두 막는 경우를 뜻합니다. 보통 말하는 '빅오'는 이 중 O입니다.

빅오를 구하는 규칙

상수와 낮은 차수의 항은 버립니다 — 3n² + 5n + 7은 n이 커질수록 n² 항이 지배하므로 O(n²)입니다. 상수 3도 증가율을 바꾸지 않아 버립니다.

순서대로 이어지면 더하고, 중첩되면 곱합니다 — O(n) 반복문 두 개가 차례로 있으면 O(n), 반복문 안에 반복문이 있으면 O(n × n) = O(n²)입니다.

가장 큰 항만 남깁니다 — O(n²)과 O(n)이 더해지면 O(n²)입니다. 입력이 커질수록 작은 항은 영향이 사라집니다.

숫자로 확인하기

n = 1,000,000일 때 연산 횟수 — log₂ n은 약 20, n은 100만, n log₂ n은 약 2천만, n²은 1조입니다. 이진 탐색은 100만 개를 뒤져도 비교가 최대 20번 안팎입니다.

초 단위로 바꾸면 — 1초에 단순 연산 1억 번을 한다고 가정하면, n = 100만에서 O(n log n)은 약 0.2초, O(n²)은 약 1만 초(2시간 40분 안팎)입니다. 이 가정은 설명용 값이고 실제 속도는 환경마다 다릅니다.

지수 시간은 작은 n에서도 폭발합니다 — 2ⁿ은 n = 30이면 약 10억(2³⁰ = 1,073,741,824), n = 60이면 약 1.15×10¹⁸입니다. n이 조금만 늘어도 현실적인 시간 안에 끝나지 않게 됩니다.

자주 하는 오해

O(n)이 O(n²)보다 항상 빠르다 — 빅오는 n이 충분히 클 때의 증가율을 비교합니다. n이 작을 때는 상수가 큰 O(n) 알고리즘이 상수가 작은 O(n²) 알고리즘보다 느릴 수 있습니다.

빅오는 최악의 경우를 뜻한다 — O는 증가율의 상한을 나타내는 수학적 표기이고, 최선·평균·최악은 입력을 어떤 경우로 보느냐를 가르는 별개의 축입니다. 최악의 경우 실행 시간에도, 평균의 경우에도 O를 쓸 수 있습니다.

반복문이 중첩되면 무조건 O(n²)이다 — 안쪽 반복이 몇 번 도는지를 세어야 합니다. 안쪽이 j = 1부터 j *= 2로 커지면 안쪽은 약 log n번이어서 전체는 O(n log n)입니다. 안쪽이 i번만 돌면 1 + 2 + … + n = n(n+1)/2 이므로 이 경우는 O(n²)입니다.

공간 복잡도는 입력 크기를 더한 값이다 — 입력 자체가 차지하는 메모리를 포함할지, 알고리즘이 추가로 쓰는 보조 공간만 셀지는 문제와 교재마다 다릅니다. 정의를 확인하고 일관되게 씁니다.

면접에서 이렇게 물어요

면접 질문

O(log n)이 되는 대표적인 예는 무엇인가요?

범위를 매번 절반으로 줄이는 이진 탐색입니다. 정렬된 배열에서 n이 두 배가 되어도 비교가 한 번 늘 뿐입니다.

면접 질문

해시 테이블 조회의 시간 복잡도는 얼마인가요?

해시 함수가 키를 고르게 흩뜨린다는 가정 아래 평균적으로 O(1)입니다. 충돌이 심하면 한 버킷에 몰려 최악에는 O(n)까지 나빠질 수 있습니다.

면접 질문

재귀로 피보나치를 구하는 코드의 복잡도는 얼마인가요?

캐시 없이 fib(n-1) + fib(n-2)를 부르면 같은 값을 반복해서 계산합니다. 호출 횟수는 정확히는 황금비 약 1.618의 n제곱에 비례하지만, O(2ⁿ)도 올바른 상한입니다. 메모이제이션을 쓰면 O(n)이 됩니다.

면접 질문

비교 기반 정렬은 왜 O(n log n)보다 빠를 수 없나요?

n개를 비교만으로 정렬하려면 가능한 순서가 n!가지이므로 결과를 가려내는 데 최악의 경우 최소 log₂(n!) = Ω(n log n)번의 비교가 필요하다고 알려져 있습니다. 그래서 병합·힙 정렬은 이 하한에 닿는 알고리즘입니다.

실제 시스템에서는

Java ArrayList — 공식 문서에 따르면 get·set은 상수 시간이고, 끝에 추가하는 add는 분할 상환 상수 시간입니다. 맨 앞에 넣으면 뒤의 원소를 모두 밀어야 해서 원소 수에 비례하는 시간이 듭니다.

Java HashMap — 공식 문서는 해시 함수가 원소를 알맞게 흩뜨린다는 가정 아래 get과 put이 상수 시간 성능을 제공한다고 설명합니다.

입력 크기가 정해진 제약 — 알고리즘 문제의 입력 제한(예: n ≤ 10⁵, 시간 제한 1초)은 어떤 복잡도까지 허용되는지 가늠하는 단서가 됩니다. n ≤ 10⁵이면 O(n²)은 약 10¹⁰번이라 보통 부족하고 O(n log n)은 여유가 있습니다.

함께 보면 좋은 토픽

이진 탐색 — O(log n)이 되는 이유를 단계별로 봅니다.

정렬 비교 — 병합·퀵·힙 정렬의 비교 횟수를 실제로 셉니다.

동적 계획법 기초 — 지수 시간이던 재귀를 메모이제이션으로 줄이는 과정을 봅니다.

투 포인터 — 이중 반복문을 한 번의 순회로 줄이는 방법을 봅니다.

P vs NP / NP-완전 — 다항 시간에 풀 수 있는 문제와 답의 검증만 다항 시간에 되는 문제를 나누는 방법을 봅니다.

에라토스테네스의 체 — 소수의 배수를 지워 n 이하의 소수를 한꺼번에 찾는 방법을 봅니다.

참고 자료

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms" 4판, 3장 "Characterizing Running Times"

ArrayList — ArrayList — Java SE 21 API

HashMap — HashMap — Java SE 21 API

Java — O(1) 상수 시간

/* ── 입력 크기가 아무리 커져도 항상 딱 한 번만 연산 ────────── */
public int getFirst(int[] arr) {
    return arr[0];   // 배열 길이와 무관하게 즉시 반환
}

배열이 10개짜리든 1,000,000개짜리든, 인덱스로 값 하나를 꺼내는 데 걸리는 연산 횟수는 항상 1번입니다.
입력 크기 n과 실행 시간이 아예 무관하기 때문에 O(1)이라고 표기합니다.

Java — O(n) 선형 시간

/* ── 배열을 한 번 훑으며 최댓값을 찾음 ─────────────────────── */
public int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {   // arr.length번 반복
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

반복문이 arr.length번, 즉 입력 크기 n만큼 정확히 한 번씩 실행됩니다.
n이 2배로 늘면 연산 횟수도 2배로 늘어나는, 입력 크기에 정비례하는 O(n) 시간복잡도입니다.

Java — O(n²) 이차 시간

/* ── 이중 for문: 모든 쌍(i, j)을 서로 비교 ─────────────────── */
public boolean hasDuplicate(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {   // i마다 arr.length번 가까이 반복
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

바깥 반복문이 n번 돌 때마다 안쪽 반복문도 매번 n번 가까이 돌기 때문에, 전체 연산 횟수는 대략 n × n번입니다.
n이 2배로 늘면 연산 횟수는 4배로 늘어나는 O(n²) 시간복잡도이며, ds-09(정렬 알고리즘)의 버블 정렬이 대표적인 예입니다.
O(log n)은 다음 토픽(이진 탐색)에서, O(2ⁿ)은 ds-10(동적 프로그래밍)의 완전 탐색에서 이미 확인했습니다.

입력 크기가 커질수록 O(1)과 O(n) 중 더 느리게 증가하는 것은?

O(1)은 입력 크기와 무관하게 일정합니다.

O(1)은 입력 크기가 커져도 실행 시간이 일정하지만, O(n)은 입력 크기에 비례해 실행 시간이 늘어납니다.

O(n^2)과 O(n log n) 중 큰 n에서 더 느린 것은?

n이 커질수록 제곱과 로그 곱셈의 격차가 벌어집니다.

O(n^2)은 n이 커질수록 O(n log n)보다 훨씬 빠르게 증가해, 큰 입력에서 더 느립니다. 그래서 정렬 알고리즘은 O(n log n)을 목표로 설계합니다.

Big-O 표기법이 나타내는 것은?

하드웨어에 따라 초 단위 시간은 다르지만 '증가 추세'는 알고리즘 고유의 특성입니다.

Big-O는 입력 크기가 커질 때 실행 시간(또는 공간)이 어떤 비율로 늘어나는지를 나타내는 점근적 표기법으로, 하드웨어 성능과 무관한 알고리즘 자체의 효율성을 비교하는 데 씁니다.