자료구조와 알고리즘을 공부하다 보면 O(1), O(n), O(log n), O(n²) 등의 표현을 자주 접하게 된다.
이들은 알고리즘의 효율성을 분석할 때 사용하는 시간 복잡도(Time Complexity)와 관련된 표기법이다.
그런데 같은 결과를 출력하는 코드라도 실행 속도가 달라지는 이유는 무엇일까? 그리고 어떤 기준으로 효율적인 알고리즘을 판단할 수 있을까?
이번 글에서는 시간 복잡도와 공간 복잡도의 개념을 이해하고, Big-O 표기법을 Python 코드와 함께 알아본다.
1. 시간 복잡도와 공간 복잡도란?
알고리즘의 효율성은 대표적으로 시간 복잡도와 공간 복잡도를 통해 분석할 수 있다.
1.1. 시간 복잡도(Time Complexity)
시간 복잡도는 입력 데이터의 크기가 증가할 때 알고리즘의 연산량이 어떻게 증가하는지 나타내는 개념이다.
예를 들어 리스트에서 특정 값을 찾는 상황을 생각해 보자.
numbers = [10, 20, 30, 40, 50]
for number in numbers:
if number == 40:
print("찾았다!")
break이 코드는 리스트의 원소를 앞에서부터 하나씩 확인한다.
찾으려는 값이 앞에 있다면 빠르게 종료되지만, 마지막에 있거나 존재하지 않는다면 모든 원소를 확인해야 한다.
데이터가 5개라면 최대 5번 비교하지만, 데이터가 1,000개라면 최대 1,000번 비교해야 할 수 있다.
즉, 입력 데이터의 개수에 비례하여 비교 횟수가 증가한다.
이러한 알고리즘의 시간 복잡도는 O(n)으로 표현할 수 있다.
여기서 n은 입력 데이터의 크기를 의미한다.
시간 복잡도에서 말하는 시간은 단순히 실제 실행 시간을 의미하지 않는다. 입력 크기에 따른 연산량의 증가 추세를 분석하기 위한 개념이다.
1.2. 공간 복잡도(Space Complexity)
공간 복잡도는 입력 데이터의 크기가 증가할 때 알고리즘이 사용하는 메모리의 양이 어떻게 증가하는지 나타내는 개념이다.
예를 들어 다음 코드를 살펴보자.
def get_first(numbers):
first = numbers[0]
return first입력 리스트에 원소가 10개 있든 10,000개 있든 함수 내부에서 추가로 사용하는 변수는 first 하나다.
따라서 입력 리스트 자체를 제외한 보조 공간 복잡도는 O(1)이다.
반면 다음 코드는 새로운 리스트를 생성한다.
def copy_list(numbers):
copied = numbers[:]
return copied원본 리스트의 원소가 n개라면 새 리스트도 n개의 원소를 저장할 공간이 필요하다.
따라서 보조 공간 복잡도는 O(n)이다.
엄밀하게는 공간 복잡도를 분석할 때 입력 데이터 자체를 포함하는지, 알고리즘이 추가로 사용하는 메모리만 계산하는지 구분해야 한다.
추가로 사용하는 공간만 분석하는 것을 보조 공간 복잡도(Auxiliary Space Complexity) 라고 한다.
2. Big-O 표기법이란?
Big-O 표기법은 입력 크기가 커질 때 알고리즘의 연산량이나 메모리 사용량이 증가하는 정도를 나타내는 수학적 표기법이다.
정확히는 어떤 함수의 증가율이 특정 함수의 상수배를 점근적으로 넘지 않는다는 상한 관계를 나타낸다.
알고리즘 분석에서는 주로 증가율의 상한을 표현하며, 관례적으로 최악의 경우에 대한 시간 복잡도를 설명할 때 많이 사용한다.
다만 Big-O 자체가 반드시 최악의 경우를 의미하는 것은 아니다.
알고리즘은 최선, 평균, 최악의 경우를 각각 분석할 수 있으며, Big-O는 그중 선택한 경우의 증가율을 나타낼 수 있다.
2.1. 상수를 생략하는 이유
다음과 같은 연산량을 가진 알고리즘을 생각해 보자.
T(n) = 3n + 5
입력 데이터가 커질수록 상수 5보다 3n의 영향이 커진다.
또한 n이 충분히 커졌을 때 상수배 3은 증가율의 종류를 바꾸지 않는다.
따라서 Big-O 표기법에서는 다음과 같이 표현한다.
O(3n + 5) = O(n)
마찬가지로 다음 수식도 살펴보자.
T(n) = 2n² + 3n + 10
n이 커질수록 n² 항이 다른 항보다 빠르게 증가한다.
따라서 가장 영향력이 큰 항을 기준으로 다음과 같이 표현한다.
O(2n² + 3n + 10) = O(n²)
이처럼 Big-O 표기법으로 알고리즘의 증가율을 간단하게 비교할 수 있다.
2.2. Big-O에서 알아야 할 주요 표기법
표기법명칭대표적인 예시
| O(1) | 상수 시간 | 리스트의 인덱스 접근 |
| O(log n) | 로그 시간 | 이진 탐색 |
| O(n) | 선형 시간 | 선형 탐색 |
| O(n log n) | 선형 로그 시간 | 병합 정렬 |
| O(n²) | 이차 시간 | 중첩 반복문 |
| O(2ⁿ) | 지수 시간 | 모든 부분집합 탐색 |
일반적으로 데이터가 충분히 커지면 O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) 순서로 증가율이 커진다.
단, Big-O는 상수항이나 실제 하드웨어의 처리 속도를 직접 반영하지 않으므로, 입력이 작을 때의 실제 실행 속도까지 보장하는 것은 아니다.
3. 시간 복잡도의 동작 원리
시간 복잡도를 이해하기 위해서는 입력 크기가 달라질 때 연산량이 어떻게 변하는지 살펴봐야 한다.
3.1. O(1) — 상수 시간
입력 데이터의 개수와 관계없이 수행되는 연산량이 일정한 경우다.
def get_first(numbers):
return numbers[0]리스트의 길이가 10이든 100만이든 첫 번째 원소를 가져오는 데 필요한 인덱스 접근 연산은 일정하다.
따라서 시간 복잡도는 O(1)이다.
3.2. O(log n) — 로그 시간
입력 크기가 증가해도 탐색 범위를 반복적으로 일정 비율만큼 줄이는 알고리즘에서 자주 나타난다.
대표적인 예시는 이진 탐색(Binary Search)이다.
이진 탐색은 정렬된 데이터의 중간값과 목표값을 비교하여 탐색 범위를 절반씩 줄여 나간다.
예를 들어 원소가 16개라면 탐색 범위가 다음과 같이 감소한다.
16 → 8 → 4 → 2 → 1
원소 수가 2배가 되더라도 필요한 단계는 대략 1단계만 증가한다.
따라서 이진 탐색의 시간 복잡도는 O(log n)이다.
Big-O에서는 로그의 밑이 상수라면 밑의 차이를 생략하므로 일반적으로 O(log n)으로 표현한다.
3.3. O(n) — 선형 시간
입력 데이터의 개수에 비례하여 연산량이 증가하는 경우다.
def print_numbers(numbers):
for number in numbers:
print(number)데이터가 n개라면 반복문이 n번 실행된다.
따라서 시간 복잡도는 O(n)이다.
3.4. O(n log n) — 선형 로그 시간
O(n log n)은 데이터를 단계적으로 분할하거나 정렬하는 알고리즘에서 자주 나타난다.
대표적으로 병합 정렬(Merge Sort)이 있다.
병합 정렬은 데이터를 반복적으로 절반씩 나누고, 다시 정렬하면서 합치는 방식으로 동작한다.
분할 단계는 약 log₂n개이며, 각 단계에서 전체 원소를 처리하는 데 O(n)의 작업이 필요하다.
따라서 전체 시간 복잡도는 O(n log n)이다.
3.5. O(n²) — 이차 시간
입력 크기의 제곱에 비례하여 연산량이 증가하는 경우다.
def print_pairs(numbers):
for a in numbers:
for b in numbers:
print(a, b)바깥 반복문이 n번 실행되고, 각 반복마다 안쪽 반복문도 n번 실행된다.
따라서 총 반복 횟수는 다음과 같다.
n × n = n²
시간 복잡도는 O(n²)이다.
예를 들어 n이 100이면 반복 횟수는 10,000번이고, n이 1,000이면 1,000,000번으로 증가한다.
4. Python 코드로 시간 복잡도 분석하기
실제 코드의 시간 복잡도를 분석할 때는 반복문과 데이터의 크기를 확인하는 것이 중요하다.
4.1. 반복문 하나
def example1(n):
for i in range(n):
print(i)반복문이 n번 실행되므로 O(n)이다.
4.2. 독립적인 반복문 두 개
def example2(n):
for i in range(n):
print(i)
for j in range(n):
print(j)첫 번째 반복문에서 n번, 두 번째 반복문에서 n번 실행되므로 총 2n번 반복한다.
상수배를 생략하면 O(n)이다.
4.3. 중첩 반복문
def example3(n):
for i in range(n):
for j in range(n):
print(i, j)총 n²번 반복하므로 O(n²)이다.
4.4. 입력 크기를 절반씩 줄이는 반복문
def example4(n):
while n > 1:
n //= 2n이 매 반복마다 절반으로 줄어든다.
따라서 시간 복잡도는 O(log n)이다.
4.5. 서로 다른 입력 크기
def example5(a, b):
for x in a:
print(x)
for y in b:
print(y)첫 번째 리스트의 길이를 n, 두 번째 리스트의 길이를 m이라고 하면 총 반복 횟수는 n + m이다.
따라서 시간 복잡도는 O(n + m)이다.
모든 반복문의 시간 복잡도를 무조건 O(n)으로 표현해서는 안 된다. 서로 다른 입력 크기를 가진다면 각각 구분해서 분석해야 한다.
5. Python에서 주요 연산의 시간 복잡도
Python에서 자주 사용하는 리스트, 딕셔너리, 집합의 대표적인 연산을 비교해 보자.
자료구조연산시간 복잡도
| list | arr[i] | O(1) |
| list | arr.append(x) | 분할 상환 O(1) |
| list | arr.pop() | O(1) |
| list | arr.insert(0, x) | O(n) |
| list | x in arr | O(n) |
| list | arr.sort() | O(n log n) |
| dict | d[key] | 평균 O(1) |
| dict | d[key] = value | 평균 O(1) |
| set | x in s | 평균 O(1) |
| deque | appendleft(x) | O(1) |
| deque | popleft() | O(1) |
여기서 분할 상환 O(1)은 개별 연산이 항상 O(1)이라는 의미가 아니다.
예를 들어 Python의 리스트는 내부 공간이 부족할 때 더 큰 저장 공간을 확보해야 하므로, 일부 append() 연산에서는 O(n)의 작업이 발생할 수 있다.
하지만 여러 번의 삽입 연산을 전체적으로 분석하면 원소 하나를 추가하는 데 드는 평균적인 비용을 O(1)로 볼 수 있다.
또한 딕셔너리와 집합은 일반적인 경우 해시를 기반으로 빠르게 동작하지만, 해시 충돌 등의 상황에서는 성능이 저하될 수 있다.
6. 시간 복잡도와 공간 복잡도의 장단점 및 선택 기준
알고리즘을 선택할 때 실행 속도만 고려해서는 안 된다.
때로는 추가 메모리를 사용하여 실행 속도를 향상시킬 수 있고, 반대로 메모리를 절약하기 위해 더 많은 연산을 수행할 수도 있다.
이러한 관계를 시간-공간 트레이드오프(Time-Space Tradeoff) 라고 한다.
6.1. 리스트를 이용한 중복 확인
def has_duplicates(numbers):
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] == numbers[j]:
return True
return False모든 서로 다른 원소 쌍을 비교하는 방식이다.
최악의 경우 시간 복잡도는 O(n²)이고, 추가로 사용하는 공간은 O(1)이다.
6.2. 집합을 이용한 중복 확인
def has_duplicates(numbers):
seen = set()
for number in numbers:
if number in seen:
return True
seen.add(number)
return False이미 확인한 원소를 집합에 저장하는 방식이다.
평균적인 경우 시간 복잡도는 O(n)이고, 보조 공간 복잡도는 O(n)이다.
즉, 추가 메모리를 사용하여 평균적인 실행 시간을 개선한 것이다.
어떤 방식이 더 좋은지는 입력 크기와 메모리 제한, 데이터의 특성에 따라 달라진다.
7. 코딩 테스트에서 시간 복잡도가 중요한 이유
코딩 테스트에서는 입력 데이터의 크기를 확인하는 것이 중요하다.
예를 들어 n이 100일 때 O(n²) 알고리즘은 약 10,000번의 반복을 수행한다.
하지만 n이 100,000이라면 약 100억 번의 반복이 발생할 수 있다.
따라서 입력 크기가 큰 문제에서는 O(n²)보다 O(n log n)이나 O(n)에 가까운 알고리즘이 필요한 경우가 많다.
다만 연산 횟수와 실제 실행 시간이 정확히 일치하는 것은 아니다. Python의 연산 종류와 자료구조, 실행 환경, 시간 제한 등을 함께 고려해야 한다.
실전 예제: 두 수의 합
정수 리스트에서 합이 목표값과 같은 두 원소가 존재하는지 확인하는 문제를 생각해 보자.
방법 1. 이중 반복문
def two_sum(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return True
return False모든 서로 다른 원소 쌍을 확인하기 때문에 최악의 경우 시간 복잡도는 O(n²)이다.
방법 2. 집합 활용
def two_sum(numbers, target):
seen = set()
for number in numbers:
if target - number in seen:
return True
seen.add(number)
return False현재 값과 더해서 목표값을 만들 수 있는 원소가 이전에 등장했는지 확인한다.
해시 연산이 평균 O(1)이라는 가정에서 전체 시간 복잡도는 평균 O(n)이며, 보조 공간 복잡도는 O(n)이다.
numbers = [2, 7, 11, 15]
print(two_sum(numbers, 9)) # True
print(two_sum(numbers, 20)) # False동일한 문제라도 어떤 자료구조와 알고리즘을 사용하는지에 따라 성능이 달라질 수 있다는 사실을 확인할 수 있다.
8. 핵심 요약
이번 글에서 살펴본 내용을 정리하면 다음과 같다.
- 시간 복잡도는 입력 크기에 따른 연산량의 증가 추세를 나타낸다.
- 공간 복잡도는 입력 크기에 따른 메모리 사용량의 증가 추세를 나타낸다.
- Big-O 표기법은 점근적인 증가율의 상한을 나타내는 방법이다.
- O(1), O(log n), O(n), O(n log n), O(n²) 등은 대표적인 복잡도 표현이다.
- 반복문이 중첩되거나 탐색 범위가 줄어드는 방식에 따라 시간 복잡도가 달라진다.
- 실행 속도를 높이기 위해 추가 메모리를 사용하는 시간-공간 트레이드오프가 존재한다.
- 코딩 테스트에서는 입력 크기와 시간·메모리 제한을 고려하여 알고리즘을 선택해야 한다.
시간 복잡도와 공간 복잡도는 앞으로 학습할 자료구조를 비교하는 중요한 기준이 된다.
자료구조의 구현 방법을 이해하는 것과 함께 주요 연산의 시간 복잡도를 분석하는 습관을 기르는 것이 좋다.
다음 글
[자료구조 03] 메모리 구조란? 스택과 힙 메모리, Python의 객체와 참조 이해하기
다음 편에서는 프로그램이 데이터를 메모리에 저장하는 방식을 살펴본다.
특히 스택 메모리와 힙 메모리의 차이, Python의 객체와 참조, 가변 객체와 불변 객체의 개념을 예제와 그림을 통해 알아본다.
자료구조 시리즈 | PART 1. 자료구조 기초 (2/5)
'자료구조 > PART 1. 자료구조 기초' 카테고리의 다른 글
| [자료구조 05] 재귀 함수란? 호출 스택과 종료 조건 이해하기 (0) | 2026.10.12 |
|---|---|
| [자료구조 04] 추상 자료형(ADT)이란? 자료구조와의 차이 이해하기 (0) | 2026.10.12 |
| [자료구조 03] 메모리 구조란? 스택과 힙 메모리, Python의 객체와 참조 이해하기 (0) | 2026.10.12 |
| [자료구조 01] 자료구조(Data Structure)란? 개념부터 종류까지 (0) | 2026.10.12 |
