두 명의 개발자가 동일한 문제를 해결하는 코드를 각각 작성했습니다. A의 코드는 100줄이고, B의 코드는 50줄입니다. 어떤 코드가 더 ‘좋은’ 코드일까요? 단순히 코드의 길이만으로는 판단할 수 없습니다. B의 코드가 더 짧고 간결해 보일지라도, 만약 입력 데이터의 양이 100만 개로 늘어났을 때 A의 코드는 1초 만에 결과를 내놓는 반면, B의 코드는 1시간이 걸린다면 어떨까요? 좋은 코드의 중요한 척도 중 하나는 바로 ‘효율성’이며, 이 효율성을 객관적으로 측정하는 도구가 바로 ‘시간 복잡도(Time Complexity)’입니다.
시간 복잡도는 알고리즘이 특정 크기의 입력(n)에 대해 작업을 완료하기까지 걸리는 ‘시간’이 얼마나 되는지를 나타내는 척도입니다. 하지만 이때의 ‘시간’은 1초, 2분과 같은 절대적인 물리적 시간이 아닙니다. 컴퓨터의 성능이나 프로그래밍 언어에 따라 실제 실행 시간은 얼마든지 달라질 수 있기 때문입니다. 대신, 시간 복잡도는 입력 데이터의 크기(n)가 증가할 때, 알고리즘의 실행 단계(연산 횟수)가 얼마나 증가하는지를 ‘증가율’의 관점에서 분석합니다.
그리고 이 증가율을 표기하는 가장 일반적인 방법이 바로 ‘빅오 표기법(Big-O Notation)’입니다. 빅오 표기법은 알고리즘의 성능을 ‘최악의 경우(Worst-case)’를 기준으로 간결하게 표현하여, 데이터가 아무리 많아져도 성능이 어느 수준 이상으로 나빠지지 않는다는 상한선을 제시합니다. 본 글에서는 이 빅오 표기법을 중심으로, 가장 대표적인 시간 복잡도 유형들(O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) 등)이 각각 무엇을 의미하며, 어떤 코드에서 나타나는지 구체적인 예시를 통해 알기 쉽게 설명하고자 합니다.
O(1) – Constant Time: 최고의 성능, 일정한 속도
핵심 개념: 입력이 늘어나도 속도는 그대로
O(1)은 ‘상수 시간 복잡도(Constant Time Complexity)’를 의미하며, 알고리즘의 성능 중 가장 이상적인 형태입니다. 이는 입력 데이터의 크기(n)가 얼마나 커지든 상관없이, 알고리즘을 완료하는 데 걸리는 시간이 항상 일정하다는 것을 의미합니다. 데이터가 1개일 때도 3번의 연산이 필요하고, 100만 개일 때도 똑같이 3번의 연산만 필요하다면, 이 알고리즘의 시간 복잡도는 O(1)입니다.
마치 자판기에서 음료수를 뽑는 것과 같습니다. 자판기 안에 음료수가 10개 있든 100개 있든, 내가 원하는 음료수의 버튼을 누르고 돈을 넣고 음료수를 받는 데 걸리는 시간은 항상 동일합니다. 내가 원하는 음료수의 위치(인덱스)를 이미 알고 있기 때문입니다.
주요 사례:
- 배열의 특정 인덱스에 있는 원소에 접근하는 경우:
arr[5] - 해시 테이블에서 특정 키(Key)를 이용해 값(Value)을 찾는 경우 (해시 충돌이 없다는 이상적인 가정 하에)
코드 예시
다음 함수는 배열의 크기와 상관없이 항상 첫 번째 원소만 반환합니다. 배열에 원소가 10개든 1000만 개든, 이 함수는 단 한 번의 연산(arr[0])만으로 작업을 완료합니다.
Python
def get_first_element(arr):
return arr[0] # 입력 크기 n에 상관없이 항상 1번의 연산
O(log n) – Logarithmic Time: 한 번에 절반씩, 놀라운 효율
핵심 개념: 데이터가 두 배로 늘어도 단계는 한 번만 추가된다
O(log n)은 ‘로그 시간 복잡도(Logarithmic Time Complexity)’를 의미하며, O(1) 다음으로 빠른, 매우 효율적인 시간 복잡도입니다. 이는 알고리즘이 문제를 해결할 때마다 탐색해야 할 데이터의 양이 절반(또는 특정 비율)씩 극적으로 줄어드는 경우에 나타납니다.
두꺼운 전화번호부에서 ‘홍길동’이라는 사람을 찾는 과정을 생각해 봅시다. 무작정 첫 페이지부터 한 장씩 넘겨보는 사람은 없을 것입니다. 우리는 보통 책의 중간쯤을 펼쳐보고, ‘홍길동’이 그 페이지보다 앞에 있는지 뒤에 있는지 판단합니다. 만약 뒤에 있다면, 앞의 절반은 더 이상 쳐다볼 필요도 없이 버립니다. 그리고 남은 절반에서 다시 중간을 펼쳐보는 과정을 반복합니다. 이처럼 매 단계마다 찾아야 할 범위가 절반으로 줄어들기 때문에, 전화번호부가 두 배로 두꺼워져도 우리는 단 한 번의 추가적인 ‘펼쳐보기’만으로 원하는 사람을 찾을 수 있습니다. 이것이 바로 로그 시간의 힘입니다.
주요 사례:
- 이진 탐색 (Binary Search)
- 균형 잡힌 트리(Balanced Tree)에서의 탐색, 삽입, 삭제
코드 예시: 이진 탐색 (Binary Search)
정렬된 배열에서 특정 값을 찾는 이진 탐색 알고리즘은 O(log n)의 대표적인 예입니다.
Python
def binary_search(sorted_arr, target):
low = 0
high = len(sorted_arr) - 1
while low <= high:
mid = (low + high) // 2 # 중간 지점 계산
if sorted_arr[mid] == target:
return mid # 값을 찾음
elif sorted_arr[mid] < target:
low = mid + 1 # 탐색 범위의 앞 절반을 버림
else:
high = mid - 1 # 탐색 범위의 뒤 절반을 버림
return -1 # 값을 찾지 못함
입력 데이터(n)가 16개일 때 최악의 경우 약 4번(16→8→4→2→1), 32개일 때 약 5번의 비교만으로 원하는 값을 찾아낼 수 있습니다. 데이터가 2배로 늘어도 연산은 1번만 추가됩니다.
O(n) – Linear Time: 정직한 비례, 선형 속도
핵심 개념: 입력이 늘어난 만큼 정확히 시간이 더 걸린다
O(n)은 ‘선형 시간 복잡도(Linear Time Complexity)’를 의미하며, 입력 데이터의 크기(n)와 실행 시간이 정비례 관계를 가질 때 나타납니다. 데이터가 100개일 때 100번의 연산이 필요하고, 200개일 때 200번의 연산이 필요하다면 이 알고리즘의 시간 복잡도는 O(n)입니다. 가장 직관적이고 흔하게 볼 수 있는 시간 복잡도 중 하나입니다.
이는 책꽂이에 꽂힌 책들 중에서 특정 제목의 책을 찾기 위해, 맨 왼쪽부터 한 권씩 차례대로 제목을 확인하는 것과 같습니다. 책이 100권이라면 최대 100번을 확인해야 하고, 200권이라면 최대 200번을 확인해야 합니다.
주요 사례:
- 반복문을 사용하여 배열의 모든 원소를 한 번씩 순회하는 경우
- 정렬되지 않은 배열에서 특정 값을 찾는 경우 (선형 탐색)
코드 예시
다음 함수는 배열에 포함된 모든 숫자의 합을 구합니다. 이를 위해서는 배열의 모든 원소를 처음부터 끝까지 단 한 번씩 방문해야 합니다. 따라서 배열의 크기가 n일 때, for 루프는 정확히 n번 반복됩니다.
Python
def calculate_sum(arr):
total_sum = 0
for number in arr: # 배열의 크기 n만큼 반복
total_sum += number
return total_sum
O(n log n) – Linearithmic Time: 정렬 알고리즘의 대표 주자
핵심 개념: 선형(n)과 로그(log n)의 효율적인 조합
O(n log n)은 ‘선형 로그 시간 복잡도(Linearithmic Time Complexity)’라고 불리며, 효율적인 정렬 알고리즘에서 가장 흔하게 나타나는 시간 복잡도입니다. 이는 전체 데이터(n)에 대해, 각 데이터를 처리할 때마다 로그(log n) 시간만큼의 연산이 추가적으로 발생하는 구조를 가집니다.
앞서 O(log n)에서 설명한 이진 탐색은 ‘정렬된’ 배열에서만 동작합니다. 그렇다면 정렬되지 않은 배열을 효율적으로 정렬하려면 어떻게 해야 할까요? 병합 정렬(Merge Sort)이나 힙 정렬(Heap Sort)과 같은 알고리즘이 바로 O(n log n)의 시간 복잡도를 가집니다. 이들 알고리즘은 거대한 문제를 작은 문제로 쪼개는 ‘분할 정복’ 방식을 사용하는데, 문제를 쪼개는 깊이가 log n에 비례하고, 각 깊이에서 모든 데이터(n)를 한 번씩 처리해야 하므로 결과적으로 n * log n의 시간이 걸리게 됩니다.
주요 사례:
- 병합 정렬 (Merge Sort)
- 힙 정렬 (Heap Sort)
- 퀵 정렬 (Quick Sort)의 평균 시간 복잡도
코드 예시: 병합 정렬 (Merge Sort)
병합 정렬은 배열을 계속해서 절반으로 나누고(이 과정의 깊이가 log n), 나눠진 배열들을 다시 합치면서 정렬하는(각 단계에서 n개의 원소를 처리) 알고리즘입니다.
Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid]) # 재귀 호출 (log n 깊이)
right_half = merge_sort(arr[mid:])
# 병합 과정 (n번의 연산)
merged_arr = []
l = h = 0
while l < len(left_half) and h < len(right_half):
if left_half[l] < right_half[h]:
merged_arr.append(left_half[l])
l += 1
else:
merged_arr.append(right_half[h])
h += 1
merged_arr += left_half[l:]
merged_arr += right_half[h:]
return merged_arr
O(n²) – Quadratic Time: 성능 저하의 시작점
핵심 개념: 데이터가 2배로 늘면 시간은 4배로 늘어난다
O(n^2)은 ‘이차 시간 복잡도(Quadratic Time Complexity)’를 의미하며, 입력 데이터의 크기(n)가 증가할 때 실행 시간이 그 제곱에 비례하여 증가하는 경우입니다. n이 10일 때 100번의 연산을, n이 100일 때 10,000번의 연산을 수행합니다. 이는 이중 반복문(nested loop) 구조에서 가장 흔하게 나타납니다.
악수 문제와 같습니다. n명의 사람이 한 방에 모였을 때, 모든 사람이 서로 한 번씩 악수를 하려면 총 몇 번의 악수가 필요할까요? 첫 번째 사람은 n-1명과 악수하고, 두 번째 사람은 나머지 n-2명과 악수하는 식으로 계산하면 약 n^2/2 번의 악수가 필요합니다. 사람 수가 2배로 늘면, 해야 할 악수의 횟수는 4배로 늘어납니다.
주요 사례:
- 이중 반복문을 사용하여 배열의 모든 원소 쌍을 비교하는 경우
- 버블 정렬 (Bubble Sort), 삽입 정렬 (Insertion Sort), 선택 정렬 (Selection Sort)
코드 예시
다음 함수는 배열 안에 중복된 값이 있는지 확인하기 위해, 배열의 모든 원소를 다른 모든 원소와 한 번씩 비교합니다. 바깥쪽 for 루프가 n번, 안쪽 for 루프가 평균 n/2번 반복되므로 전체 연산 횟수는 n^2에 비례합니다.
Python
def has_duplicates(arr):
n = len(arr)
for i in range(n): # 바깥 루프: n번 반복
for j in range(i + 1, n): # 안쪽 루프: 평균 n/2번 반복
if arr[i] == arr[j]:
return True
return False
n이 10,000을 넘어가기 시작하면 이 알고리즘의 성능은 눈에 띄게 저하되기 시작합니다.
O(2ⁿ) – Exponential Time: 피해야 할 위험한 속도
핵심 개념: 데이터가 하나 늘 때마다 시간은 두 배로 늘어난다
O(2^n)은 ‘지수 시간 복잡도(Exponential Time Complexity)’를 의미하며, 입력 데이터의 크기(n)가 1 증가할 때마다 실행 시간이 두 배씩 늘어나는, 매우 비효율적인 알고리즘입니다. 이는 재귀 호출이 일어날 때마다 하나의 문제가 두 개 이상의 새로운 하위 문제로 나뉘는 경우에 주로 발생합니다.
비밀번호를 추측하는 경우를 생각해 봅시다. 비밀번호가 1자리 숫자라면 10번만 시도하면 되지만, 2자리라면 100번, 3자리라면 1000번을 시도해야 합니다. 이처럼 자릿수(n)가 하나 늘어날 때마다 찾아야 할 경우의 수가 거듭제곱으로 폭발적으로 증가하는 것이 지수 시간의 특징입니다.
주요 사례:
- 동적 계획법이나 메모이제이션 없이 재귀적으로 피보나치 수열을 계산하는 경우
- 집합의 모든 부분집합을 구하는 문제
코드 예시
메모이제이션 기법을 사용하지 않은 순수한 재귀 방식의 피보나치 함수는 O(2^n)의 시간 복잡도를 가집니다. fib(n)을 계산하기 위해 fib(n-1)과 fib(n-2)를 모두 호출해야 하고, 이 과정이 연쇄적으로 일어나기 때문입니다.
Python
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
n이 40만 되어도 이 함수의 실행 시간은 몇 초 이상 걸리게 되며, n이 100 정도 되면 슈퍼컴퓨터로도 현실적인 시간 안에 계산하기 어렵습니다.
시간 복잡도 비교: 한눈에 보기
| Big-O | 명칭 | 성능 | n = 10 | n = 100 |
| O(1) | 상수 시간 | Excellent | 1 | 1 |
| O(log n) | 로그 시간 | Good | ~3 | ~7 |
| O(n) | 선형 시간 | Fair | 10 | 100 |
| O(n log n) | 선형 로그 시간 | Fair | ~33 | ~664 |
| O(n²) | 이차 시간 | Bad | 100 | 10,000 |
| O(n³) | 삼차 시간 | Bad | 1,000 | 1,000,000 |
| O(2ⁿ) | 지수 시간 | Very Bad | 1,024 | 1.26 x 10³⁰ |
| O(n!) | 팩토리얼 시간 | Very Bad | 3,628,800 | 9.33 x 10¹⁵⁷ |
그래프에서 볼 수 있듯이, n이 커질수록 O(n^2) 이상의 시간 복잡도를 가진 알고리즘의 실행 시간은 감당할 수 없을 정도로 급격하게 증가합니다. 따라서 효율적인 알고리즘을 설계한다는 것은, 가능한 한 O(n log n) 이하의 시간 복잡도를 갖도록 문제를 해결하는 방법을 찾는 과정이라고 할 수 있습니다.
마무리: 좋은 개발자의 기본 소양
시간 복잡도를 이해하는 것은 단순히 알고리즘 문제를 풀기 위한 이론이 아닙니다. 이것은 내가 작성한 코드가 실제 서비스 환경에서 수많은 사용자와 대용량 데이터를 마주했을 때 어떻게 동작할지를 예측하고, 발생할 수 있는 성능 문제를 사전에 방지하는 ‘예지력’을 갖게 해주는 핵심적인 기본 소양입니다.
코드를 작성할 때, “이 코드 블록은 데이터가 100만 개일 때 몇 번이나 반복될까?”라는 질문을 스스로에게 던지는 습관을 들이는 것이 중요합니다. 특히 반복문, 그중에서도 중첩된 반복문은 시간 복잡도를 크게 증가시키는 주범이므로 항상 주의 깊게 살펴봐야 합니다. 시간 복잡도에 대한 깊은 이해는 여러분을 단순히 ‘동작하는 코드’를 짜는 개발자를 넘어, ‘효율적이고 확장 가능한 코드’를 짜는 뛰어난 개발자로 성장시켜 줄 것입니다.