시간 복잡도
기술노트
시간 복잡도 (Time Complexity)
시간 복잡도(Time Complexity)는 알고리즘의 효율성을 분석하기 위한 객관적인 척도입니다. 입력 데이터의 크기(n)가 증가함에 따라 알고리즘의 실행 시간이 얼마나 증가하는지를 나타내며, 주로 빅오(Big-O) 표기법을 사용하여 최악의 경우(Worst-Case)를 기준으로 표현합니다.
📈 대표적인 빅오(Big-O) 표기법과 예시
- O(1) (Constant Time) : 입력 크기 `n`에 관계없이 실행 시간이 일정합니다.
> * '예시': 배열의 특정 인덱스 접근, 해시 테이블에서 키를 이용한 값 조회 (해시 충돌이 없는 이상적인 경우).
- O(log n) (Logarithmic Time) : 실행 시간이 `n`의 로그에 비례하여 증가합니다. 데이터의 크기가 두 배로 늘어나도, 연산 횟수는 한 번만 늘어나는 특징을 가집니다.
> * '예시': 이진 탐색 (Binary Search), 균형 잡힌 이진 탐색 트리(BST)에서의 원소 탐색.
- O(n) (Linear Time) : 실행 시간이 입력 크기 `n`에 정비례하여 증가합니다.
> * '예시': 배열의 모든 요소를 순회하는 반복문, 연결 리스트(Linked List) 탐색.
- O(n log n) (Linearithmic Time) : 실행 시간이 `n`과 `log n`의 곱에 비례합니다. 효율적인 정렬 알고리즘에서 흔히 볼 수 있습니다.
> * '예시': 병합 정렬 (Merge Sort), 힙 정렬 (Heap Sort), 퀵 정렬 (Quick Sort)의 평균 시간 복잡도.
- O(n²) (Quadratic Time) : 실행 시간이 `n`의 제곱에 비례합니다. 주로 중첩된 반복문에서 나타납니다.
> * '예시': 이중 반복문을 이용한 배열 탐색, 버블 정렬 (Bubble Sort), 삽입 정렬 (Insertion Sort).
- O(2ⁿ) (Exponential Time) : 실행 시간이 `n`에 대해 지수적으로 증가합니다. `n`이 조금만 커져도 실행 시간이 기하급수적으로 늘어나므로, 다른 접근법을 찾는 것이 좋습니다.
> * '예시': 피보나치 수열의 단순 재귀적 계산, 집합의 모든 부분 집합을 구하는 문제.
🤔 왜 시간 복잡도가 중요한가?
- 알고리즘 선택의 기준 : 동일한 문제를 해결하는 여러 알고리즘 중, 예상되는 입력 데이터의 크기와 분포에 따라 가장 효율적인 것을 선택하는 객관적 척도를 제공합니다.
- 성능 예측 및 확장성 : 코드 작성 단계에서부터 알고리즘의 성능 한계를 예측하고, 데이터가 증가함에 따라 시스템이 어떻게 반응할지(확장성) 가늠할 수 있습니다.
- 최적화의 방향 제시 : 시간 복잡도 분석을 통해 코드의 어느 부분이 비효율적인지(병목 현상) 식별하고 최적화의 우선순위를 정할 수 있습니다.
💡 개발자 핵심 Point
- 빅오 표기법은 가장 큰 영향을 주는 항만을 고려하며, 계수는 무시합니다. 예를 들어, `O(3n² + 2n + 5)`는 `n`이 무한히 커질 때 `n²`의 영향이 가장 크므로 `O(n²)`로 단순화하여 표현합니다.
- 시간 복잡도는 '최선(Best, Ω)', '평균(Average, Θ)', '최악(Worst, O)'의 경우로 나눌 수 있지만, 일반적으로는 '최악의 경우'를 기준으로 알고리즘의 성능을 보장하는 빅오 표기법을 주로 사용합니다.
- 공간 복잡도(Space Complexity)는 알고리즘 실행 시 필요한 메모리 양을 나타내는 척도로, 시간 복잡도와 함께 알고리즘의 효율성을 평가하는 중요한 기준입니다.
- 현업에서는 라이브러리나 프레임워크의 내부 동작 원리를 이해하고, 특정 함수나 메서드가 어떤 시간 복잡도를 가지는지 파악하는 것이 중요합니다. 예를 들어, Python의 리스트에서 `append`는 O(1)이지만, `insert(0, ...)`는 O(n)의 비용이 발생합니다.
