알고리즘 시간 복잡도 완벽 가이드 - Big O 표기법부터 실전 분석까지

프로그래밍에서 알고리즘의 효율성을 측정하는 것은 매우 중요합니다. 동일한 문제를 해결하더라도 어떤 알고리즘을 선택하느냐에 따라 프로그램의 성능이 크게 달라질 수 있습니다. 이 글에서는 알고리즘 분석의 핵심인 시간 복잡도와 Big O 표기법에 대해 자세히 알아보겠습니다.

시간 복잡도란 무엇인가

**시간 복잡도(Time Complexity)**는 입력 크기에 따라 알고리즘이 실행되는 데 필요한 시간을 나타내는 척도입니다. 실제 실행 시간은 하드웨어, 프로그래밍 언어, 컴파일러 등 다양한 요소에 영향을 받기 때문에, 우리는 연산의 횟수를 기준으로 효율성을 측정합니다.

왜 시간 복잡도가 중요한가

작은 데이터에서는 알고리즘 간 차이가 미미할 수 있습니다. 하지만 데이터가 커지면 그 차이는 극적으로 벌어집니다.

import time

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

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

arr = list(range(10000000))
target = 9999999

start = time.time()
linear_search(arr, target)
print(f"Linear Search: {time.time() - start:.4f}s")

start = time.time()
binary_search(arr, target)
print(f"Binary Search: {time.time() - start:.6f}s")

Big O 표기법의 이해

Big O 표기법은 알고리즘의 최악의 경우(Worst Case) 성능을 나타냅니다. 입력 크기 n이 무한대로 커질 때 연산 횟수의 증가율을 표현합니다.

주요 시간 복잡도 종류

표기법	명칭	예시
O(1)	상수 시간	배열 인덱스 접근
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	단순 반복문
O(n log n)	선형 로그 시간	병합 정렬, 퀵 정렬
O(n2)	이차 시간	버블 정렬, 중첩 반복문
O(2n)	지수 시간	피보나치 재귀

O(1) - 상수 시간

입력 크기와 관계없이 항상 일정한 시간이 소요됩니다.

def get_first_element(arr):
    return arr[0] if arr else None

def is_even(n):
    return n % 2 == 0

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

이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 정렬되지 않은 배열에서는 먼저 정렬을 수행해야 합니다.

O(n) - 선형 시간

입력 크기에 비례하여 시간이 증가합니다.

def find_max(arr):
    if not arr:
        return None
    
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    
    return max_val

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

O(n2) - 이차 시간

중첩된 반복문에서 자주 나타납니다.

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

def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

O(n2) 알고리즘은 데이터가 커지면 매우 느려집니다. n=10,000일 때 약 1억 번의 연산이 필요합니다.

시간 복잡도 분석 방법

규칙 1: 상수는 무시한다

O(2n)은 O(n)으로, O(500)은 O(1)로 표기합니다.

def example(arr):
    total = 0
    for num in arr:
        total += num
    for num in arr:
        total += num * 2
    return total

규칙 2: 최고 차수만 남긴다

O(n2 + n)은 O(n2)로 표기합니다.

def complex_function(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])
    
    for item in arr:
        print(item)

규칙 3: 반복문 분석

def nested_loop(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

def logarithmic_loop(n):
    count = 0
    i = 1
    while i < n:
        count += 1
        i *= 2
    return count

공간 복잡도

시간 복잡도와 함께 **공간 복잡도(Space Complexity)**도 중요합니다. 알고리즘이 사용하는 메모리 양을 나타냅니다.

def sum_array_in_place(arr):
    total = 0
    for num in arr:
        total += num
    return total

def create_doubled_array(arr):
    result = []
    for num in arr:
        result.append(num * 2)
    return result

함수	시간 복잡도	공간 복잡도
sum_array_in_place	O(n)	O(1)
create_doubled_array	O(n)	O(n)

실전 예제: 정렬 알고리즘 비교

퀵 정렬 - O(n log n)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

병합 정렬 - 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

코딩 테스트에서의 활용

코딩 테스트에서 시간 제한을 맞추기 위해서는 입력 크기에 따른 적절한 알고리즘 선택이 필수입니다.

입력 크기 n	허용 가능한 복잡도
n < 10	O(n!)
n < 20	O(2n)
n < 500	O(n3)
n < 5,000	O(n2)
n < 100,000	O(n log n)
n < 10,000,000	O(n)
n > 10,000,000	O(log n), O(1)

일반적으로 1초에 약 1억 번의 연산이 가능하다고 가정합니다. 문제의 시간 제한과 입력 크기를 확인하여 알고리즘을 선택하세요.

마무리

시간 복잡도를 이해하면 효율적인 알고리즘을 설계하고 선택할 수 있습니다. 핵심 포인트를 정리하면 다음과 같습니다.

Big O 표기법은 최악의 경우 성능을 나타낸다
상수와 낮은 차수는 무시한다
입력 크기에 따라 적절한 알고리즘을 선택한다
시간과 공간의 트레이드오프를 고려한다

다음 글에서는 자료구조별 시간 복잡도와 실전 문제 풀이에 대해 다루겠습니다.