시간 복잡도와 공간 복잡도 쉽게 이해하기

왜 실행 시간만으로는 부족할까

같은 코드를 실행해도 어떤 컴퓨터에서는 1초가 걸리고, 다른 컴퓨터에서는 3초가 걸릴 수 있습니다. 프로그래밍 언어, 컴퓨터 성능, 실행 환경에 따라 실제 시간은 달라집니다. 그래서 알고리즘을 비교할 때는 "몇 초 걸리는가"보다 "입력이 커질수록 일이 얼마나 늘어나는가"를 봅니다.

예를 들어 학생 10명 중에서 이름을 찾는 일은 금방 끝납니다. 하지만 학생이 100만 명이라면 이야기가 달라집니다. 같은 방식으로 찾더라도 확인해야 할 사람이 훨씬 많아집니다. 알고리즘의 성능을 볼 때 중요한 질문은 이것입니다.

입력이 10배 커지면, 해야 할 일도 10배 커지는가? 100배 커지는가? 아니면 거의 그대로인가?

이 질문에 답하기 위해 사용하는 개념이 시간 복잡도입니다. 시간 복잡도는 입력 크기가 커질 때 실행 시간이 얼마나 빠르게 증가하는지를 나타내는 방법입니다.

여기서 입력 크기를 보통 n이라고 부릅니다. 배열에 숫자가 100개 있으면 n = 100입니다. 문자열 길이가 50이면 n = 50입니다. 문제마다 n이 의미하는 대상은 다르지만, 공통점은 "처리해야 할 데이터의 크기"라는 점입니다.

AI 생성 이미지

시간 복잡도는 반복 횟수를 보는 것이다

초보자는 시간 복잡도를 어렵게 느끼지만, 처음에는 이렇게 생각하면 충분합니다.

시간 복잡도는 코드가 대략 몇 번 반복되는지 보는 방법이다.

다음 코드는 배열에서 가장 큰 값을 찾습니다.

max_value = numbers[0]

for x in numbers:
    if x > max_value:
        max_value = x

배열에 숫자가 5개 있으면 반복문은 5번 돕니다. 숫자가 100개 있으면 100번 돕니다. 숫자가 n개 있으면 n번 돕니다. 그래서 이 알고리즘의 시간 복잡도는 O(n)입니다.

O 표기법은 입력 크기 n이 커질 때 필요한 일의 증가 정도를 간단히 나타내는 표기입니다. 정확히 몇 번 실행되는지보다 증가하는 모양을 봅니다.

예를 들어 어떤 코드가 3n + 10번 정도 실행된다고 합시다. n이 아주 커지면 +10은 전체 흐름에 큰 영향을 주지 않습니다. 3n에서 숫자 3도 "대략 n에 비례한다"는 성질을 바꾸지는 않습니다. 그래서 3n + 10은 보통 O(n)으로 표현합니다.

입력 크기에 따라 차이는 크게 벌어진다

작은 입력에서는 대부분의 알고리즘이 빨라 보입니다. 그러나 입력이 커지면 차이가 급격히 벌어집니다.

이 표에서 중요한 것은 숫자의 정확성보다 증가 속도입니다. O(n²)은 n이 1,000,000일 때 현실적으로 감당하기 어렵습니다. 반면 O(log n)은 입력이 매우 커져도 천천히 증가합니다.

그래서 어떤 코드는 작은 데이터에서는 잘 작동하지만 큰 데이터에서는 실패합니다. 코드가 틀린 것이 아니라, 입력 크기에 비해 반복 횟수가 너무 빠르게 늘어나는 방식일 수 있습니다.

O(1): 입력 크기와 상관없이 일정한 경우

O(1)은 입력이 커져도 실행 횟수가 거의 변하지 않는 경우입니다. 배열의 첫 번째 값을 읽는 코드를 생각해 봅시다.

first = numbers[0]

배열에 값이 10개 있어도 첫 번째 값만 읽습니다. 값이 100만 개 있어도 첫 번째 값만 읽습니다. 처리할 일이 입력 크기와 상관없이 일정하므로 O(1)입니다.

일상 예시로는 책의 첫 페이지를 펴는 일이 있습니다. 책이 100쪽이든 1,000쪽이든 첫 페이지를 펴는 동작은 거의 같습니다.

주의할 점은 O(1)이 "무조건 1번 실행된다"는 뜻은 아니라는 것입니다. 5번 실행될 수도 있고 10번 실행될 수도 있습니다. 핵심은 입력 크기가 커져도 실행 횟수가 함께 커지지 않는다는 점입니다.

O(n): 데이터를 한 번 훑는 경우

O(n)은 입력 크기에 비례해서 일이 늘어나는 경우입니다. 배열에서 특정 값이 있는지 확인하는 코드를 봅시다.

found = false

for x in numbers:
    if x == target:
        found = true
        break

배열의 원소가 n개라면 최악의 경우 n개를 모두 확인해야 합니다. 그래서 O(n)입니다.

여기서 "최악의 경우"라는 말을 기억해야 합니다. 찾는 값이 첫 번째에 있으면 금방 끝날 수 있습니다. 하지만 값이 없거나 마지막에 있다면 전부 확인해야 합니다. 알고리즘을 분석할 때는 보통 가장 힘든 경우를 기준으로 생각합니다. 그래야 큰 입력에서도 안전한지 판단할 수 있습니다.

O(n²): 중첩 반복문이 만드는 빠른 증가

O(n²)은 보통 반복문 안에 또 반복문이 있을 때 자주 등장합니다.

for i in range(0, n):
    for j in range(0, n):
        print(i, j)

바깥 반복문이 n번 돌고, 그때마다 안쪽 반복문도 n번 돕니다. 전체 반복 횟수는 n × n, 즉 n²입니다.

작은 예시로 n = 3이면 다음과 같은 조합이 만들어집니다.

(0, 0), (0, 1), (0, 2)
(1, 0), (1, 1), (1, 2)
(2, 0), (2, 1), (2, 2)

총 9번입니다. n = 1000이면 1,000,000번입니다. 중첩 반복문은 입력이 조금만 커져도 실행 횟수가 빠르게 늘어납니다.

하지만 중첩 반복문이라고 항상 O(n²)은 아닙니다. 다음처럼 바깥 반복문은 n번, 안쪽 반복문은 항상 3번만 돈다면 전체는 O(n)입니다.

for i in range(0, n):
    for j in range(0, 3):
        print(i, j)

반복문 모양만 보지 말고, 각 반복문이 입력 크기와 어떤 관계인지 확인해야 합니다.

O(log n): 절반씩 줄이는 경우

O(log n)은 입력 크기를 한 번에 많이 줄이는 알고리즘에서 자주 나옵니다. 대표적인 예가 정렬된 배열에서 값을 찾는 이진 탐색입니다.

이진 탐색은 가운데 값을 확인한 뒤, 찾는 값이 더 작으면 오른쪽 절반을 버리고 왼쪽만 봅니다. 더 크면 왼쪽 절반을 버리고 오른쪽만 봅니다. 한 번 비교할 때마다 후보가 절반으로 줄어듭니다.

left = 0
right = n - 1

while left <= right:
    mid = (left + right) // 2

    if numbers[mid] == target:
        return mid
    elif numbers[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

입력이 1,000,000개여도 절반씩 줄이면 약 20번 정도면 충분합니다. 그래서 O(log n)은 매우 빠른 편입니다.

여기서 log n은 "n을 몇 번 절반으로 나누면 1에 가까워지는가"라고 이해하면 됩니다. 수학 기호가 어렵게 느껴진다면 처음에는 이렇게만 기억해도 괜찮습니다.

절반씩 줄이면 O(log n)이다.

O(n log n): 한 번 훑는 일을 여러 단계 반복하는 경우

O(n log n)은 정렬 알고리즘에서 자주 만납니다. 예를 들어 데이터를 계속 반으로 나누고, 각 단계에서 전체 데이터를 한 번씩 처리하는 방식입니다.

직관적으로는 이렇게 볼 수 있습니다.

데이터를 반으로 나눈다
각 묶음을 다시 반으로 나눈다
충분히 작아지면 다시 합치며 정리한다
각 단계에서 전체 n개를 한 번씩 처리한다

반으로 나누는 단계 수는 O(log n)입니다. 각 단계에서 전체 데이터를 처리하는 비용은 O(n)입니다. 그래서 전체는 O(n log n)이 됩니다.

O(n log n)은 O(n)보다는 느리지만 O(n²)보다는 훨씬 빠릅니다. 많은 효율적인 정렬 알고리즘이 이 정도 성능을 목표로 합니다.

공간 복잡도: 메모리를 얼마나 쓰는가

알고리즘의 성능은 시간만으로 판단하지 않습니다. 프로그램이 실행되는 동안 메모리를 얼마나 사용하는지도 중요합니다. 이것을 공간 복잡도라고 합니다.

공간 복잡도도 입력 크기 n에 따라 필요한 메모리가 어떻게 증가하는지를 봅니다. 특히 알고리즘을 비교할 때는 입력으로 이미 주어진 데이터 말고, 실행 중에 새로 더 사용하는 메모리인 추가 공간을 따로 살펴보는 경우가 많습니다.

다음 코드는 배열의 합을 구합니다.

total = 0

for x in numbers:
    total = total + x

입력 배열을 제외하고 새로 사용하는 값은 total 하나뿐입니다. numbers의 크기가 커져도 추가 메모리는 거의 일정합니다. 그래서 추가 공간 복잡도는 O(1)입니다.

반면 다음 코드는 원래 배열의 각 값을 두 배로 만든 새 배열을 만듭니다.

result = []

for x in numbers:
    result.append(x * 2)

입력이 n개이면 결과 배열도 n개가 됩니다. 새로 필요한 메모리가 입력 크기에 비례하므로 추가 공간 복잡도는 O(n)입니다.

시간을 줄이기 위해 메모리를 더 쓰는 경우

알고리즘에서는 시간을 줄이기 위해 메모리를 더 쓰는 선택을 자주 합니다.

예를 들어 어떤 배열에 특정 값이 있는지 여러 번 확인해야 한다고 합시다.

방법 1은 매번 배열을 처음부터 끝까지 확인하는 것입니다.

for q in queries:
    found = false
    for x in numbers:
        if x == q:
            found = true
            break

질문이 m개이고 배열 크기가 n이면 최악의 경우 O(m × n)이 걸립니다.

방법 2는 먼저 값을 빠르게 찾을 수 있는 집합에 넣어 두는 것입니다.

seen = set()

for x in numbers:
    seen.add(x)

for q in queries:
    if q in seen:
        print("있음")

처음에 집합을 만드는 데 O(n)의 시간이 들고, 집합을 저장하기 위해 O(n)의 메모리를 더 씁니다. 대신 각 질문에 답하는 시간은 보통 매우 짧아집니다. 질문이 많을수록 두 번째 방법이 유리합니다.

이처럼 좋은 알고리즘은 단순히 "가장 빠른 코드"가 아닙니다. 시간과 메모리의 균형을 보고 현재 문제에 맞는 선택을 하는 것이 중요합니다.

복잡도를 추정하는 기본 순서

코드를 볼 때 시간 복잡도를 추정하는 순서는 다음처럼 잡으면 좋습니다.

1. 입력 크기 n이 무엇인지 정한다.

2. 입력 크기에 따라 반복 횟수가 변하는 부분을 찾는다.

3. 반복문이 한 번 도는지, 중첩되는지, 절반씩 줄어드는지 본다.

4. 가장 크게 증가하는 항만 남긴다.

5. 상수 배수와 작은 덧셈은 과감히 버린다.

예를 들어 다음 코드를 봅시다.

for x in numbers:
    print(x)

for i in range(0, n):
    for j in range(0, n):
        print(i, j)

첫 번째 반복문은 O(n)입니다. 두 번째 중첩 반복문은 O(n²)입니다. 전체는 O(n + n²)이지만, n이 커질수록 n²이 훨씬 더 큰 영향을 줍니다. 그래서 전체 시간 복잡도는 O(n²)입니다.

자주 틀리는 부분

첫째, 실제 실행 시간과 시간 복잡도를 혼동하기 쉽습니다. O(n) 코드가 항상 O(n²) 코드보다 빠른 것은 아닙니다. 입력이 아주 작으면 O(n²) 코드도 충분히 빠를 수 있습니다. 하지만 입력이 커질수록 O(n)이 더 안정적입니다.

둘째, 반복문 개수만 세고 반복 범위를 보지 않는 실수가 많습니다. 반복문이 두 개 있어도 서로 따로 실행되면 O(n + n), 즉 O(n)입니다. 반대로 반복문이 하나여도 그 안에서 비싼 작업을 반복하면 더 큰 비용이 될 수 있습니다.

셋째, 공간 복잡도를 잊기 쉽습니다. 새 배열, 집합, 해시 테이블을 만들면 시간이 줄어들 수 있지만 메모리는 더 필요합니다. 입력 크기가 매우 크다면 메모리 제한 때문에 실패할 수도 있습니다.

넷째, log n을 수학 공식처럼 외우려고 하면 어렵습니다. 처음에는 "절반씩 줄어드는가?"만 확인하면 됩니다. 이진 탐색처럼 후보를 계속 반으로 버릴 수 있다면 O(log n)을 떠올리면 됩니다.

핵심 정리

시간 복잡도는 입력 크기 n이 커질 때 실행 시간이 얼마나 빠르게 늘어나는지 보는 방법입니다. 공간 복잡도는 입력 크기가 커질 때 필요한 메모리가 얼마나 늘어나는지 보는 방법입니다.

가장 자주 만나는 형태는 다음과 같습니다.

알고리즘을 배울 때 복잡도는 단순한 시험용 지식이 아닙니다. 문제의 입력 크기를 보고 어떤 풀이가 가능한지 판단하는 도구입니다. 작은 데이터에서 맞는 코드가 큰 데이터에서도 통과할지는 복잡도를 보면 어느 정도 예측할 수 있습니다.