시간 복잡도란? 각 복잡도의 특징과 Python 구현 예제

시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 걸리는 시간의 증가 양상을 나타내는 지표입니다. 주로 입력 데이터의 크기(n)가 커질수록 알고리즘이 얼마나 더 느려지는지를 평가하는 데 사용됩니다. 시간 복잡도는 Big-O 표기법으로 표현되며, 일반적으로 알고리즘의 최악의 경우를 나타냅니다.

이번 포스팅에서는 대표적인 시간 복잡도 유형들을 설명하고, 각 시간 복잡도에 해당하는 간단한 Python 코드 예제를 통해 이를 이해해보겠습니다.

1. O(1) - 상수 시간 복잡도

특징

• 입력 크기와 관계없이 항상 일정한 시간이 소요됩니다.
• 배열의 특정 인덱스에 접근하거나, 스택의 push/pop 연산 등이 해당됩니다.

구현

def constant_time(arr):
    return arr[0]  # 배열의 첫 번째 요소 반환

# 테스트
arr = [1, 2, 3, 4, 5]
print(constant_time(arr))  # 출력: 1

2. 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

# 테스트
sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(sorted_arr, 7))  # 출력: 3
print(binary_search(sorted_arr, 10))  # 출력: -1

3. O(n) - 선형 시간

특징

• 입력 크기에 비례하여 실행 시간이 선형적으로 증가합니다.
• 배열 순회, 선형 검색 등이 해당됩니다.

구현 - 선형 검색

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

# 테스트
arr = [4, 2, 7, 1, 9, 5]
print(linear_search(arr, 7))  # 출력: 2
print(linear_search(arr, 3))  # 출력: -1

4. 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, 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

# 테스트
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # 출력: [3, 9, 10, 27, 38, 43, 82]

5. O(n^2) - 이차 시간

특징

• 입력 크기의 제곱에 비례하여 실행 시간이 증가합니다.
• 중첩된 반복문, 단순한 정렬 알고리즘(버블 정렬, 선택 정렬 등)이 해당됩니다.

구현 - 버블 정렬

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

# 테스트
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))  # 출력: [11, 12, 22, 25, 34, 64, 90]

6. O(2^n) - 지수 시간

특징

• 입력 크기가 증가함에 따라 실행 시간이 기하급수적으로 증가합니다.
• 재귀적 피보나치 수열, 부분집합 생성 등이 해당됩니다.

구현 - 재귀적 피보나치

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

# 테스트
for i in range(10):
    print(f"fibonacci({i}) = {fibonacci(i)}")