시간 복잡도는 알고리즘의 효율성을 수학적으로 표현하는 방법으로, 입력 크기에 따른 실행 시간의 증가율을 나타냅니다.

---

시간 복잡도를 알아보기 전에 알고리즘 분석에 대해 먼저 살펴보겠습니다.

알고리즘 분석 (Algorithm Analysis)

알고리즘 분석은 알고리즘의 효율성을 수학적으로 평가하고 비교하는 방법입니다.

좋은 알고리즘을 만드는 것도 중요하지만, 그것이 얼마나 효율적인지 측정하고 개선하는 것도 똑같이 중요합니다.

---

🎯 알고리즘 분석이란?

왜 알고리즘을 분석하는가?

지금까지 다양한 알고리즘 설계 기법을 배웠습니다. 이제는 만든 알고리즘이 얼마나 좋은지 평가할 차례입니다.

실생활 비유:

자동차를 만들었다면:
- 빠르기는? (성능)
- 연료는 얼마나? (효율성)
- 공간은 얼마나? (크기)

알고리즘도 마찬가지:
- 얼마나 빠른가? → 시간 복잡도
- 메모리는 얼마나? → 공간 복잡도
- 최악의 경우는? → 최악/평균/최선 분석

두 가지 핵심 질문:

1. 이 알고리즘은 얼마나 빠른가?  →  시간 복잡도 (Time Complexity)

2. 이 알고리즘은 메모리를 얼마나 쓰는가?  → 공간 복잡도 (Space Complexity)

알고리즘 분석의 목적

1. 알고리즘 비교

문제: 정렬
방법 A: 버블 정렬
방법 B: 병합 정렬

어느 것이 더 빠른가? → 시간 복잡도 비교

A: O(n²)
B: O(n log n)

→ B가 더 빠름!

2. 성능 예측

현재: 100개 데이터 처리 (1초)
미래: 10,000개 데이터 처리 (?)

알고리즘이 O(n²)이면:
→ (10,000/100)² = 10,000배 → 약 2.7시간 예상

알고리즘이 O(n)이면:
→ 10,000/100 = 100배  → 약 100초 예상

3. 최적화 방향 결정

병목 지점 발견:
- 어느 부분이 느린가?
- 개선 가능한가?
- 트레이드오프는?

예: 시간 vs 공간  →  메모리를 더 써서 시간을 줄일 수 있나?

분석의 종류

1. 점근적 분석 (Asymptotic Analysis)

입력 크기(n)가 충분히 클 때의 성능

왜 "충분히 클 때"?
- 작은 입력에서는 차이 미미
- 큰 입력에서 차이 극명

예:
n=10: O(n)과 O(n²) 차이 작음
n=10000: O(n)과 O(n²) 차이 엄청남

2. 최선/평균/최악 분석

같은 알고리즘도 입력에 따라 다름

퀵 정렬:
- 최선: O(n log n) (피벗이 항상 중간)
- 평균: O(n log n)
- 최악: O(n²) (피벗이 항상 끝)

어느 것으로 평가?
→ 보통 최악의 경우 (안전)

3. 상각 분석 (Amortized Analysis)

여러 연산의 평균 비용

예: 동적 배열
대부분: O(1) 삽입
가끔: O(n) 확장

평균적으로: O(1)

표기법

알고리즘 성능을 수학적으로 표현하는 방법:

Big-O (상한): "빅 오"로 읽음, 알고리즘의 실행 시간이 "아무리 느려도 이보다는 빨라"

O(g(n)): "최악의 경우 g(n)보다 느리지 않다"

가장 많이 사용
예: 이진 탐색은 O(log n)

Big-Ω (하한): "빅 오메가"로 읽음, 알고리즘의 실행 시간이 "아무리 빨라도 이보다는 느려"

Ω(g(n)): "최선의 경우 g(n)보다 빠르지 않다"

최소 성능 보장
예: 비교 기반 정렬은 최소 Ω(n log n)

Big-Θ (상한 = 하한): "빅 세타"로 읽음, 알고리즘의 실행 시간이 "평균적으로 딱 이만큼 걸려"

Θ(g(n)): "항상 g(n)에 비례"

정확한 복잡도
예: 배열 전체 순회는 Θ(n)

이 파트에서 배울 내용

1. 시간 복잡도
   - Big-O 표기법
   - 주요 복잡도 (O(1), O(n), O(n²), ...)
   - 복잡도 계산 방법

2. 공간 복잡도
   - 메모리 사용량
   - 시간-공간 트레이드오프
   - 재귀의 공간 복잡도

3. 점근적 표기법
   - Big-O, Big-Ω, Big-Θ
   - 수학적 정의
   - 증명 방법

4. 최선/평균/최악 분석
   - 입력에 따른 성능 차이
   - 평균 케이스 분석
   - 확률적 분석

5. 상수 계수와 실제 성능
   - 이론 vs 실제
   - 캐시, 메모리 접근
   - 실무 고려사항

6. 상각 분석
   - 평균 비용 계산
   - 동적 배열, 스택
   - 잠재 함수 방법

7. 복잡도 클래스
   - P, NP, NP-Complete
   - 계산 복잡도 이론
   - 다루기 어려운 문제들

실무에서의 중요성

왜 분석이 중요한가?

작은 데이터 (n < 100):
- 어떤 알고리즘이든 빠름
- 코드 간결성이 더 중요

큰 데이터 (n > 100,000):
- 알고리즘 선택이 결정적
- O(n²)는 불가능
- O(n log n) 필수

예:
n = 100,000
O(n log n): 1초
O(n²): 2.7시간!

실무 의사결정:

상황 1: 실시간 검색 → O(log n) 필수 (이진 탐색, 트리)

상황 2: 배치 처리 → O(n log n) 허용 (정렬 + 처리)

상황 3: 메모리 제한 → 공간 복잡도 우선 (스트리밍)

상황 4: 한 번만 실행 → 구현 간단한 것 (O(n²)도 OK)

---

이제 알고리즘 분석의 첫 번째 주제인 시간 복잡도를 자세히 알아봅시다.

---

🎯 시간 복잡도란 무엇인가

알고리즘 성능의 척도

알고리즘을 만들었다면, 그것이 얼마나 빠른지 평가해야 합니다.

왜 시간 복잡도가 필요한가?

두 정렬 알고리즘:
A: 10개 데이터를 1초에 정렬
B: 10개 데이터를 2초에 정렬

A가 더 빠르다?

100만 개 데이터라면?
A: 100,000초 (약 28시간)
B: 200초 (약 3분)

B가 훨씬 빠름!

→ 절대 시간이 아닌 "증가율"이 중요

시간 복잡도의 의미:

알고리즘의 실행 시간이 입력 크기(n)에 따라 어떻게 증가하는가?

예:
- 선형 증가 (n배)
- 제곱 증가 (n²배)
- 로그 증가 (log n배)

실생활 비유

책에서 이름 찾기:

방법 1: 처음부터 한 장씩
→ 책이 두 배 두꺼우면 시간도 두 배
→ 선형 증가 (O(n))

방법 2: 이진 탐색
→ 책이 두 배 두꺼워도 1번만 더
→ 로그 증가 (O(log n))

방법 3: 모든 쌍 비교
→ 책이 두 배 두꺼우면 시간은 네 배
→ 제곱 증가 (O(n²))

측정 방법

1. 실제 측정 (X)

import time

start = time.time()
sort_algorithm(data)
end = time.time()
print(f"실행 시간: {end - start}초")

문제점:

• 컴퓨터 성능에 따라 다름
• 입력 데이터에 따라 다름
• 일반화 어려움

2. 연산 횟수 계산 (O)

def linear_search(arr, target):
    comparisons = 0
    for item in arr:
        comparisons += 1  # 비교 연산
        if item == target:
            return comparisons
    return comparisons

# 연산 횟수 = n번

장점:

• 하드웨어 독립적
• 일반적 성능 파악
• 알고리즘 비교 가능

---

📊 Big-O 표기법

Big-O란?

Big-O 표기법은 알고리즘의 시간 복잡도를 표현하는 수학적 표기법입니다.

정의:

f(n) = O(g(n))

의미:
"n이 충분히 클 때, f(n)은 g(n)에 비례하여 증가한다"

예:
f(n) = 3n² + 2n + 1
→ O(n²)

큰 항만 남기고, 계수 제거

왜 이렇게?

f(n) = 3n² + 2n + 1

n = 10:     3×100 + 2×10 + 1 = 321
n = 100:    3×10000 + 2×100 + 1 = 30201
n = 1000:   3×1000000 + 2×1000 + 1 = 3002001

n이 클수록:
- n² 항이 지배적
- 2n, 1은 무시 가능
- 계수 3도 무시 (비율만 중요)

따라서: O(n²)

주요 시간 복잡도

복잡도 계층:

빠름 ←──────────────────────────────→ 느림

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

상수      로그     선형       선형로그      제곱       지수     팩토리얼

증가율 비교
| 복잡도 | n=10 | n=100 | n=1,000 | n=10,000 |
|--------|------|-------|---------|----------|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1,000 | 10,000 |
| O(n log n) | 30 | 700 | 10,000 | 130,000 |
| O(n²) | 100 | 10,000 | 1,000,000 | 100,000,000 |
| O(2ⁿ) | 1,024 | 1.3×10³⁰ | - | - |
| O(n!) | 3,628,800 | - | - | - |

:

🔍 복잡도별 예시

O(1) - 상수 시간

정의: 입력 크기와 무관하게 일정한 시간

def get_first_element(arr):
    """
    O(1) - 상수 시간

    배열 크기와 무관
    """
    return arr[0]  # 한 번의 접근

def hash_lookup(hash_table, key):
    """
    O(1) - 해시 테이블 조회
    """
    return hash_table[key]

# 예시
arr = [1, 2, 3, 4, 5, ... , 1000000]
first = get_first_element(arr)  # 항상 같은 시간

특징:

• 가장 빠름
• 입력 크기 증가해도 시간 동일

O(log n) - 로그 시간

정의: 입력이 절반씩 줄어들 때

def binary_search(arr, target):
    """
    O(log n) - 이진 탐색

    매번 절반씩 줄어듦
    """
    left, right = 0, len(arr) - 1

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

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반만
        else:
            right = mid - 1  # 왼쪽 절반만

    return -1

# 분석:
# n = 1000 → 10번
# n = 1000000 → 20번
# n이 1000배 증가해도 10번만 더!

특징:

• 매우 효율적
• 분할 정복 알고리즘에서 흔함

O(n) - 선형 시간

정의: 입력 크기에 비례

def linear_search(arr, target):
    """
    O(n) - 선형 탐색

    모든 원소 확인
    """
    for i, item in enumerate(arr):  # enumerate(arr): 리스트 arr에서 '인덱스(i)'와 '내용(item)'을 동시에 꺼내주는 함수
        if item == target:
            return i
    return -1       # 리스트 arr 전체에서 target를 못 찾았다면, "없음"을 뜻하는 약속된 신호인 -1을 반환

def find_max(arr):
    """
    O(n) - 최댓값 찾기
    """
    max_val = arr[0]
    for num in arr:  # n번 반복
        if num > max_val:
            max_val = num
    return max_val

# 분석:
# n = 100 → 100번
# n = 1000 → 1000번
# n이 10배 → 시간도 10배

특징:

• 가장 흔한 복잡도
• 모든 데이터를 봐야 할 때

O(n log n) - 선형로그 시간

정의: 분할 정복 + 합치기

def merge_sort(arr):
    """
    O(n log n) - 병합 정렬

    분할: O(log n)
    합치기: O(n)
    """
    if len(arr) <= 1:
        return arr

    # 분할 (log n 레벨)
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 합치기 (n번)
    return merge(left, right)

def merge(left, right):
    """두 정렬된 배열 합치기 - O(n)"""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 분석:
# 레벨: log n
# 각 레벨에서 n번 작업
# 총: n × log n

특징:

• 효율적인 정렬 알고리즘
• O(n)보다 느리지만 O(n²)보다 빠름

O(n²) - 제곱 시간

정의: 이중 반복문

def bubble_sort(arr):
    """
    O(n²) - 버블 정렬

    이중 반복문
    """
    n = len(arr)

    for i in range(n):          # n번
        for j in range(n - 1):  # n번
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

def find_duplicates(arr):
    """
    O(n²) - 모든 쌍 비교
    """
    duplicates = []

    for i in range(len(arr)):        # n번
        for j in range(i + 1, len(arr)):  # n번
            if arr[i] == arr[j]:
                duplicates.append(arr[i])

    return duplicates

# 분석:
# n = 10 → 100번
# n = 100 → 10,000번
# n = 1000 → 1,000,000번

특징:

• 작은 데이터에는 OK
• 큰 데이터에는 느림

O(2ⁿ) - 지수 시간

정의: 입력마다 선택지가 2배

def fibonacci_recursive(n):
    """
    O(2ⁿ) - 순수 재귀 피보나치

    매번 2개로 분기
    """
    if n <= 1:
        return n

    # 2개로 분기
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# 분석:
# fib(5):
#           fib(5)
#          /      \
#      fib(4)    fib(3)
#      /    \    /    \
#   fib(3) fib(2) ...
#
# 호출 횟수: 2^5 = 32번

# n = 10 → 1,024번
# n = 20 → 1,048,576번
# n = 30 → 1,073,741,824번!

특징:

• 매우 느림
• 작은 n도 불가능
• 동적 계획법으로 개선 필요

O(n!) - 팩토리얼 시간

정의: 모든 순열

def permutations_naive(arr):
    """
    O(n!) - 모든 순열 생성

    n개 원소의 순열: n!개
    """
    if len(arr) <= 1:
        return [arr]

    result = []
    for i in range(len(arr)):
        # 나머지 원소의 순열
        rest = arr[:i] + arr[i+1:]
        for perm in permutations_naive(rest):
            result.append([arr[i]] + perm)

    return result

# 분석:
# n = 3 → 6개 (3!)
# n = 5 → 120개 (5!)
# n = 10 → 3,628,800개 (10!)

특징:

• 가장 느림
• n > 15면 실용적으로 불가능

---

🔢 복잡도 계산 연습

기본 규칙

1. 순차 실행: 더하기

def example1(arr):
    # O(n)
    for x in arr:
        print(x)

    # O(n)
    for x in arr:
        print(x * 2)

    # 총: O(n) + O(n) = O(2n) = O(n)
    # 계수 제거!

2. 중첩 실행: 곱하기

def example2(arr):
    # 외부: O(n)
    for i in arr:
        # 내부: O(n)
        for j in arr:
            print(i, j)

    # 총: O(n) × O(n) = O(n²)

3. 큰 항만 남기기

def example3(arr):
    # O(n)
    for x in arr:
        print(x)

    # O(n²)
    for i in arr:
        for j in arr:
            print(i, j)

    # 총: O(n) + O(n²) = O(n²)
    # 큰 항만!

예제 분석

예제 1:

def example(arr):
    # 1번 연산
    result = arr[0]  # O(1)

    # n번 반복
    for x in arr:  # O(n)
        result += x

    return result

# 총: O(1) + O(n) = O(n)

예제 2:

def example(arr):
    count = 0

    # n번 반복
    for i in range(len(arr)):
        # n번 반복
        for j in range(i):
            count += 1

    return count

# 분석:
# i=0: 0번
# i=1: 1번
# i=2: 2번
# ...
# i=n-1: n-1번
# 총: 0+1+2+...+(n-1) = n(n-1)/2 = O(n²)

예제 3:

def example(arr):
    # log n번 반복 (절반씩)
    i = 1
    while i < len(arr):
        # n번 반복
        for j in range(len(arr)):
            print(i, j)
        i *= 2

    return

# 총: O(log n) × O(n) = O(n log n)

예제 4:

def example(n):
    # n번
    for i in range(n):
        print(i)

    # n²번 (이중 반복)
    for i in range(n):
        for j in range(n):
            print(i, j)

    # log n번 (절반씩)
    i = 1
    while i < n:
        print(i)
        i *= 2

    return

# 총: O(n) + O(n²) + O(log n) = O(n²)
# 가장 큰 항만!

---

💡 실무 팁

복잡도별 특성

🟢 효율적 (실용적으로 사용 가능)

O(1) - 상수 시간

• 📊 성장률: 입력 크기와 무관
• 🔍 예시: 해시 테이블 조회, 배열 인덱스 접근
• ⏱️ n=1,000,000 → 1번의 연산

O(log n) - 로그 시간

• 📊 성장률: 매우 완만
• 🔍 예시: 이진 탐색, 균형 이진 트리 탐색
• ⏱️ n=1,000,000 → 약 20번의 연산

O(n) - 선형 시간

• 📊 성장률: 선형 증가
• 🔍 예시: 배열 순회, 단순 반복문
• ⏱️ n=1,000,000 → 1,000,000번의 연산

🟡 주의 필요 (중간 효율)

O(n log n) - 선형 로그 시간

• 📊 성장률: 선형보다 약간 가파름
• 🔍 예시: 병합 정렬, 퀵 정렬(평균), 힙 정렬
• ⏱️ n=1,000,000 → 약 20,000,000번의 연산

🔴 비효율적 (작은 데이터만 가능)

O(n²) - 이차 시간

• 📊 성장률: 급격한 증가
• 🔍 예시: 버블 정렬, 삽입 정렬, 이중 반복문
• ⏱️ n=1,000 → 1,000,000번의 연산
• ⚠️ n > 10,000이면 실용적이지 않음

O(2ⁿ) - 지수 시간

• 📊 성장률: 폭발적 증가
• 🔍 예시: 피보나치(재귀), 부분집합 생성
• ⏱️ n=30 → 1,073,741,824번의 연산
• ⚠️ n > 20이면 거의 불가능

O(n!) - 팩토리얼 시간

• 📊 성장률: 최악의 증가율
• 🔍 예시: 순열 생성, 외판원 문제(브루트 포스)
• ⏱️ n=10 → 3,628,800번의 연산
• ⚠️ n > 12이면 실질적으로 불가능

실용적 가이드라인

• ✅ O(1), O(log n), O(n): 대부분의 실용적인 알고리즘
• ⚠️ O(n log n): 효율적인 정렬 알고리즘의 한계
• ⚠️ O(n²): 작은 데이터셋에서만 사용 가능
• ❌ O(2ⁿ), O(n!): n이 20을 넘으면 실용적으로 사용 불가능

---

📊 데이터 크기별 허용 시간 복잡도

데이터 크기 (n)	O(log n)	O(n)	O(n log n)	O(n²)	O(n³)	O(2ⁿ)	O(n!)
≤ 10	✅ 최적	✅ 최적	✅ 최적	✅ 가능	✅ 가능	✅ 가능	✅ 가능
≤ 20	✅ 최적	✅ 최적	✅ 최적	✅ 가능	✅ 가능	✅ 가능	❌ 불가
≤ 100	✅ 최적	✅ 최적	✅ 최적	✅ 가능	✅ 가능	❌ 불가	❌ 불가
≤ 1,000	✅ 최적	✅ 최적	✅ 최적	✅ 가능	⚠️ 한계	❌ 불가	❌ 불가
≤ 10,000	✅ 최적	✅ 최적	✅ 권장	⚠️ 한계	❌ 불가	❌ 불가	❌ 불가
≤ 100,000	✅ 최적	✅ 최적	✅ 권장	❌ 불가	❌ 불가	❌ 불가	❌ 불가
≤ 1,000,000	✅ 최적	✅ 필수	✅ 권장	❌ 불가	❌ 불가	❌ 불가	❌ 불가
> 1,000,000	✅ 최적	✅ 필수	⚠️ 한계	❌ 불가	❌ 불가	❌ 불가	❌ 불가

범례

• ✅ 최적: 가장 효율적인 선택
• ✅ 권장: 실용적으로 충분히 빠름
• ✅ 필수: 이보다 느린 알고리즘은 시간 초과
• ✅ 가능: 실행 가능하나 더 빠른 방법 권장
• ⚠️ 한계: 시간 초과 위험이 있음
• ❌ 불가: 실행 시간이 너무 오래 걸림

최적화 전략

1. 불필요한 반복 제거

# 나쁜 예: O(n²)
def has_duplicate_bad(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if i != j and arr[i] == arr[j]:
                return True
    return False

# 좋은 예: O(n)
def has_duplicate_good(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

2. 적절한 자료구조

# 나쁜 예: O(n) 검색
def search_in_list(lst, target):
    return target in lst  # O(n)

# 좋은 예: O(1) 검색
def search_in_set(s, target):
    return target in s  # O(1)

3. 사전 계산

# 나쁜 예: 매번 계산
def sum_queries_bad(arr, queries):
    results = []
    for l, r in queries:
        # 매 쿼리마다 O(r-l)
        results.append(sum(arr[l:r]))
    return results

# 좋은 예: 누적합
def sum_queries_good(arr, queries):
    # 사전 계산: O(n)
    prefix = [0]
    for x in arr:
        prefix.append(prefix[-1] + x)

    # 각 쿼리: O(1)
    results = []
    for l, r in queries:
        results.append(prefix[r] - prefix[l])
    return results

성능 측정

import time

def measure_time(func, *args): # func: 측정하고 싶은 함수
                               # *args: "가변 인자"로 func가 실행될 때 필요한 재료(배열, 타겟 값 등)를 몇 개든 유연하게 받음
    """함수 실행 시간 측정"""
    start = time.time()
    result = func(*args)
    end = time.time()
    print(f"{func.__name__}: {end - start:.6f}초")  # func.__name__: 실행된 함수의 이름을 자동으로 출력
    return result

# 사용
arr = list(range(10000))
measure_time(bubble_sort, arr.copy())  # O(n²)
measure_time(merge_sort, arr.copy())   # O(n log n)

---

🎯 핵심 정리

Big-O 표기법

f(n) = O(g(n))

의미: n이 클 때 f(n)은 g(n)에 비례

특징:
- 큰 항만
- 계수 제거
- 최악의 경우

주요 복잡도

O(1)        상수       가장 빠름
O(log n)    로그       매우 빠름
O(n)        선형       빠름
O(n log n)  선형로그   괜찮음
O(n²)       제곱       느림
O(2ⁿ)       지수       매우 느림
O(n!)       팩토리얼   극도로 느림

계산 규칙

순차: O(f) + O(g) = O(max(f, g))
중첩: O(f) × O(g) = O(f × g)

실무 지침

작은 데이터 (n < 100):
- 복잡도 덜 중요
- 코드 간결성 우선

큰 데이터 (n > 10,000):
- 복잡도 매우 중요
- O(n log n) 이하 필수

---

🔗 다음 글에서는

[07-02] 공간 복잡도 (Space Complexity)

• 공간 복잡도의 개념: 알고리즘이 사용하는 메모리 양
• 시간-공간 트레이드오프: 메모리를 더 써서 시간 절약하기
• 재귀의 공간 복잡도: 호출 스택의 깊이 이해
• 제자리 알고리즘: 추가 공간 없이 동작하는 효율적 방법

---

이전 글: [06-09] 문자열 알고리즘
다음 글: [07-02] 공간 복잡도
시리즈: P1. Computer Science