시간 복잡도란 무었인가?

개발자로 일하다 보면 "효율적인 코드란 무엇일까?"라는 질문을 자주 접하게 됩니다. 이때 핵심 키워드가 바로 시간 복잡도(Time Complexity)입니다. 시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간과 입력 데이터 크기 간의 관계를 나타냅니다.
이번 글에서는 시간 복잡도를 이해하기 쉽게 설명하고, 간단한 예시를 통해 효율적인 알고리즘 설계의 중요성을 이야기해보겠습니다.

---

시간 복잡도란?

시간 복잡도는 알고리즘이 처리해야 할 작업량이 데이터 크기에 따라 어떻게 증가하는지를 수학적으로 표현한 것입니다. 주로 빅오 표기법(Big-O Notation)을 사용하며, 아래와 같은 표현들이 있습니다:

• O(1): 입력 크기에 상관없이 항상 일정한 시간.
• O(log N): 입력 크기가 증가할수록 작업량이 천천히 증가.
• O(N): 데이터 크기만큼 작업량이 증가.
• O(N^2): 데이터 크기의 제곱에 비례해 작업량 증가.

빅오 표기법은 최악의 경우(Worst Case)를 기준으로 계산합니다. 즉, 알고리즘이 가장 비효율적으로 동작할 때의 성능을 나타내죠.

---

예시로 이해하는 시간 복잡도

예제 1: 배열에서 특정 값 찾기

문제: 길이가 ( N )인 배열에서 숫자 x가 있는지 확인하라.

1. 직접 탐색 (O(N))

    def find_x(arr, x):
        for num in arr:
            if num == x:
                return True
        return False

   • 이 코드는 배열의 첫 번째부터 마지막 요소까지 순차적으로 탐색합니다.
   • 최악의 경우, 배열의 모든 요소를 확인해야 하므로 시간 복잡도는 O(N)입니다.

2. 이진 탐색 (O(log N))
   배열이 정렬되어 있다고 가정했을 때, 이진 탐색을 사용할 수 있습니다:

    def binary_search(arr, x):
        low, high = 0, len(arr) - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == x:
                return True
            elif arr[mid] < x:
                low = mid + 1
            else:
                high = mid - 1
        return False

   • 이 방법은 배열을 반으로 나누며 탐색합니다.
   • 데이터 크기가 ( N )일 때 비교 횟수는 약 ( \log_2 N )번이므로 O(log N)입니다.
   • 입력 크기가 커질수록 선형 탐색(O(N))보다 훨씬 빠릅니다.

예제 2: 두 배열의 중복 요소 찾기

문제: 두 배열 ( A )와 ( B )에서 공통 요소를 찾아라.

1. 이중 반복문 (O(N^2))

    def find_common_elements(a, b):
        common = []
        for x in a:
            for y in b:
                if x == y:
                    common.append(x)
        return common

   • 각 배열의 요소를 비교하기 때문에 시간 복잡도는 O(N^2)입니다.
   • 배열 크기가 클수록 비효율적입니다.

2. 집합(Set) 활용 (O(N))

    def find_common_elements(a, b):
        set_a = set(a)
        set_b = set(b)
        return list(set_a & set_b)

   • Python의 set은 해시 테이블로 구현되어, 중복 체크와 교집합 연산이 매우 빠릅니다.
   • 시간 복잡도는 O(N + M)으로 배열 크기만큼만 연산이 필요합니다.

---

시간 복잡도의 중요성

시간 복잡도는 단순한 코딩 문제가 아닌, 실제 제품 성능에도 영향을 미칩니다. 예를 들어:

• 검색 엔진: 사용자가 검색어를 입력하면 수백만 개의 문서 중에서 관련 결과를 찾아야 합니다. 효율적인 검색 알고리즘이 필수입니다.
• 추천 시스템: 스트리밍 서비스에서 사용자가 좋아할 콘텐츠를 추천하는 작업은 수백만 명의 사용자 데이터를 처리해야 합니다.

비효율적인 알고리즘은 시스템 과부하를 유발하고, 사용자 경험을 저하시킬 수 있습니다.

---

마무리하며

시간 복잡도는 코드를 작성할 때 효율성을 판단하는 중요한 기준입니다. 단순히 "동작하는 코드"를 넘어, "효율적인 코드"를 작성하려면 시간 복잡도를 고려한 알고리즘 설계가 필수적입니다.

코드 작성 시, "내 코드가 입력 데이터 크기 변화에 따라 얼마나 효율적으로 동작할까?"라는 질문을 항상 던져보세요. 이런 사고방식이 여러분을 더 나은 개발자로 성장시킬 것입니다.