시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘의 효율성을 판단할 때 가장 기본이 되는 개념이다. 이는 입력값의 크기(N)가 커질 때 프로그램이 문제를 해결하기 위해 수행해야 하는 연산의 양을 의미한다. 단순히 코드가 빨리 실행되는지 느린지를 말하는 게 아니라, 입력이 커질수록 연산 횟수가 얼마나 늘어나는가를 수학적으로 표현하는 것이다.

예를 들어 반 친구 중에서 가장 키가 큰 사람을 찾는다고 생각해보자. 한 명씩 살펴보며 현재까지의 최대값을 갱신하는 방식은 전체 학생 수(N)만큼의 비교가 필요하다. 즉, 입력값 N이 커질수록 실행 횟수도 비례해 늘어나므로 시간 복잡도는 O(N)이다. 반면 모든 학생을 서로 비교하는 방식이라면, 한 사람당 다른 모든 사람과 비교해야 하므로 N×N, 즉 O(N²)의 시간이 걸린다. 이 두 방식은 모두 같은 문제를 해결하지만, N이 커질수록 실행 시간의 차이는 급격히 벌어진다. 이것이 바로 시간 복잡도의 의미다.

시간 복잡도는 보통 Big-O 표기법(Big-O Notation) 으로 표현한다. Big-O는 알고리즘의 실행 시간이 입력 크기에 따라 얼마나 증가하는지를 보여주는 상한선이다. 입력 크기가 커져도 실행 시간이 거의 변하지 않으면 O(1), 입력 크기에 비례하면 O(N), 로그 형태로 느리게 증가하면 O(log N), 정렬 알고리즘처럼 N log N 형태로 증가하면 O(N log N), 중첩 반복문처럼 제곱으로 증가하면 O(N²)이라고 표현한다. 만약 모든 경우를 재귀적으로 탐색하는 알고리즘이라면 O(2ⁿ)이나 O(N!)처럼 훨씬 가파르게 증가한다.

코드로 간단히 살펴보면 다음과 같다.

# O(N) - 한 번 순회
for num in array:
    print(num)

# O(N²) - 중첩 순회
for a in array:
    for b in array:
        print(a, b)

첫 번째 코드는 입력 크기 N에 비례해서 실행되므로 O(N)이고, 두 번째 코드는 N×N번 실행되므로 O(N²)이다. 반복문이 한 단계 중첩될 때마다 차수가 하나씩 늘어난다고 보면 된다.

시간 복잡도를 계산할 때는 보통 상수를 생략하고, 입력이 커질수록 가장 빠르게 증가하는 항만 남긴다. 예를 들어 2N² + N은 O(N²)로, 3N + 5는 O(N)으로 단순화한다. 왜냐하면 입력이 커질수록 상수항과 낮은 차수의 영향은 거의 사라지기 때문이다. 결국 우리가 알고 싶은 건 “입력 크기가 커질 때 전체 실행 시간이 얼마나 빨리 커지느냐”다.

예를 들어 배열에서 최댓값을 찾는 함수를 생각해보자. 첫 번째 방법은 모든 원소를 서로 비교한다.

def find_max_num(array):
    for num in array:
        is_max = True
        for compare in array:
            if num < compare:
                is_max = False
        if is_max:
            return num

이 함수는 모든 원소가 다른 모든 원소와 비교되므로 O(N²)이다. 반면, 한 번만 순회하면서 현재까지의 최댓값을 갱신하는 방법은 훨씬 효율적이다.

def find_max_num(array):
    max_num = array[0]
    for num in array:
        if num > max_num:
            max_num = num
    return max_num

이 코드는 입력 크기만큼 한 번 순회하므로 O(N)이다. 입력값이 커질수록 첫 번째 방법은 훨씬 느려진다.

시간 복잡도를 이해한다는 건 단순히 O(N²), O(N)을 외우는 게 아니다. 입력이 커질 때 실행 횟수가 어떤 패턴으로 늘어나는지를 감각적으로 파악하는 것이다. 좋은 알고리즘은 입력이 두 배가 되어도 실행 시간이 두 배 정도로만 늘어나지만, 비효율적인 알고리즘은 입력이 조금만 커져도 시간이 폭발적으로 늘어난다.

정리하자면, 시간 복잡도는 입력 크기 대비 연산량의 증가율을 의미한다. 중첩된 반복문은 차수를 높이고, 상수나 낮은 차수는 무시한다. 효율적인 코드는 일반적으로 O(N)이나 O(N log N) 수준을 목표로 하며, 입력이 커져도 급격히 느려지지 않는다. 결국 시간 복잡도를 이해하는 것은 단순히 코드를 빠르게 만드는 기술이 아니라, 입력이 커질수록 알고리즘이 얼마나 안정적으로 작동하는지를 판단하는 사고방식이다.