알고리즘 복잡도 완벽 가이드 (Algorithmic Complexity)

1. 알고리즘 복잡도란?

알고리즘 복잡도(Algorithmic Complexity)는 문제를 해결하기 위해 알고리즘이 필요로 하는 컴퓨팅 자원을 수학적으로 표현한 것이다.

• 시간 복잡도(Time Complexity) → 알고리즘 실행 시간
• 공간 복잡도(Space Complexity) → 알고리즘이 차지하는 메모리

복잡도를 줄이는 것이 곧 효율적인 알고리즘을 만드는 핵심이다. 보통 Big O 표기법을 사용해 입력 크기(n)에 따른 성능 변화를 분석한다.

---

2. 시간 복잡도 vs 공간 복잡도

• 시간(Time) → 알고리즘이 실행되는 데 걸리는 연산 시간
• 공간(Space) → 알고리즘이 실행 중 사용하는 메모리

💡 시간과 공간은 종종 상충한다.
실행 속도를 높이려면 메모리를 더 쓰게 되고, 메모리를 절약하면 실행 속도가 느려질 수 있다.
이를 공간-시간 트레이드오프(Space-Time Tradeoff) 라고 한다.

---

3. 복잡도 계산 방법

복잡도 계산은 보통 최악의 경우(worst-case)를 기준으로 한다.

• 연산 횟수를 입력 크기 n의 함수로 표현
• 가장 큰 차수의 항만 남기고 나머지는 무시

예시:

• n개의 항목을 반복 처리(5n) + 상수 연산(3) → O(n)

---

4. 표기법 정리

Big O (O-notation)

• 상한선을 제공 → 최악의 경우 실행 시간
• 예: O(1), O(n), O(n²)

Big Θ (Theta notation)

• 상·하한선을 동시에 제공 → 실행 시간의 정확한 성장률
• 예: θ(n²) → 정확히 n²에 비례

Big Ω (Omega notation)

• 하한선 제공 → 최선의 경우 실행 시간
• 예: Ω(n) → 최소 선형 시간은 걸림

---

5. 복잡도 종류별 예시 (Python 코드 포함)

O(1) - 상수 시간

입력 크기와 관계없이 항상 일정한 시간에 수행된다.

def get_first_element(arr):
    return arr[0]  # 인덱스로 바로 접근 → O(1)

print(get_first_element([1, 2, 3]))

---

O(log n) - 로그 시간

입력 크기를 매번 절반으로 줄이는 알고리즘.

def binary_search(arr, target):
    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

print(binary_search([1, 3, 5, 7, 9], 7))

---

O(n) - 선형 시간

모든 원소를 한 번씩 확인한다.

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

print(linear_search([1, 3, 5, 7, 9], 5))

---

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

효율적인 정렬 알고리즘에서 자주 등장.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    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

print(merge_sort([5, 2, 9, 1, 5, 6]))

---

O(n²) - 이차 시간

중첩 반복문을 사용하는 경우.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([5, 2, 9, 1, 5, 6]))

---

O(2^n) - 지수 시간

입력 크기에 따라 실행 시간이 기하급수적으로 증가.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

---

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

모든 경우의 수를 완전 탐색.

import itertools

def traveling_salesman(cities):
    shortest_path = None
    shortest_distance = float('inf')
    for path in itertools.permutations(cities):
        distance = sum(abs(path[i] - path[i + 1]) for i in range(len(cities) - 1))
        if distance < shortest_distance:
            shortest_distance = distance
            shortest_path = path
    return shortest_path, shortest_distance

print(traveling_salesman([1, 2, 3]))

---

6. 마무리

알고리즘 복잡도를 이해하면

• 문제에 맞는 효율적인 알고리즘 선택
• 성능 최적화 방향 설정
• 메모리와 실행 시간의 균형 조정

이 가능해진다. 앞으로 알고리즘을 설계할 때는 단순히 “잘 동작하는 코드”가 아니라, 성능까지 고려한 코드를 목표로 해야 한다.