시간 복잡도: 알고리즘 성능의 핵심 개념

1. 시간 복잡도란?

시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 필요한 연산 횟수를 입력 크기(n)에 따라 분석하는 개념입니다. 즉, 프로그램이 실행될 때 입력 크기가 커질수록 연산량이 어떻게 변하는지를 나타냅니다.

이 개념은 알고리즘의 효율성을 평가하는 중요한 기준이 됩니다. 예를 들어, 같은 문제를 해결하는 두 개의 알고리즘이 있다면, 시간 복잡도가 더 낮은 알고리즘이 실행 속도가 빠르고 성능이 우수합니다.

---

2. 시간 복잡도의 표기법: Big-O 표기법

시간 복잡도는 보통 Big-O 표기법으로 표현됩니다. 이는 최악의 경우를 기준으로 연산량을 분석하는 방법입니다.

주요 시간 복잡도 종류 및 설명

표기법의미

O(1)	상수 시간 - 입력 크기와 상관없이 실행 시간이 일정함
O(log n)	로그 시간 - 입력 크기가 커질수록 증가 속도가 느림
O(n)	선형 시간 - 입력 크기에 비례하여 실행 시간이 증가함
O(n log n)	로그-선형 시간 - 비교 기반 정렬 알고리즘의 평균적인 시간 복잡도
O(n²)	이차 시간 - 중첩된 반복문에서 자주 발생
O(2ⁿ)	지수 시간 - 피보나치 수열을 재귀적으로 계산할 때 발생
O(n!)	팩토리얼 시간 - 순열을 생성하는 알고리즘에서 발생

---

3. 대표적인 알고리즘과 시간 복잡도 분석

3.1 O(1) - 상수 시간 알고리즘

// 배열의 첫 번째 원소를 출력하는 함수 (O(1))
int getFirstElement(int[] arr) {
    return arr[0];
}

설명: 입력 크기와 상관없이 항상 일정한 시간이 걸리므로 O(1)입니다.

3.2 O(n) - 선형 시간 알고리즘

// 배열의 모든 원소의 합을 계산하는 함수 (O(n))
int sum(int[] arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

설명: 배열의 크기가 증가할수록 실행 시간이 선형적으로 증가합니다.

 

3.3 O(n²) - 이차 시간 알고리즘

// 버블 정렬 (O(n²))
void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

설명: 이중 반복문을 사용하므로 실행 시간이 입력 크기의 제곱에 비례하여 증가합니다.

---

4. 시간 복잡도 시각화

시간 복잡도별 성능 차이를 직관적으로 이해하기 위해 아래와 같은 그래프를 참고하세요.

위 그래프에서 볼 수 있듯이 O(1)과 O(log n)은 매우 빠르지만, O(n²) 이상의 복잡도는 입력 크기가 조금만 커져도 실행 시간이 급격히 증가합니다.

---

5. 실전에서 시간 복잡도 최적화 방법

1. 반복문 줄이기: 중첩된 반복문을 단일 반복문으로 변경
2. 효율적인 자료구조 사용: 해시맵(HashMap), 트리(Tree) 등의 자료구조 활용
3. 메모이제이션 활용: 같은 연산을 반복하지 않고 저장하여 활용 (Dynamic Programming)
4. 정렬 및 탐색 알고리즘 선택: O(n log n) 정렬 알고리즘(퀵 정렬, 병합 정렬) 사용

---

6. 결론

시간 복잡도는 알고리즘의 효율성을 분석하는 중요한 척도입니다. 이를 이해하고 적절한 알고리즘을 선택하면 성능 최적화에 큰 도움이 됩니다. 단순히 코드가 돌아가는 것에 만족하지 않고, 최적의 성능을 고민하는 습관을 가지는 것이 중요합니다.