시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘이 실행되는데 필요한 연산 횟수를 입력 크기 NN에 따라 분석하는 것입니다. 이를 통해 알고리즘의 효율성을 비교하고, 입력 크기가 증가했을 때의 성능을 예측할 수 있습니다. 아래는 시간 복잡도를 계산하는 기본 방법과 개념입니다.

 

 

1. 시간 복잡도 계산의 기본 원칙

1. 가장 많이 반복되는 연산을 기준으로 계산합니다.
2. 상수 시간은 무시합니다 (예: O(1)+O(N)→O(N)).
3. 가장 높은 차수의 연산만 남깁니다 (예: O(N^2+N)→O(N2)).

 

2. 시간 복잡도 분석 단계

(1) 반복문 확인

반복문이 실행되는 횟수를 기반으로 복잡도를 계산합니다.

예제 1: 단일 반복문

for (int i = 0; i < N; i++) {
    // O(1): 한 번 실행
}

• 반복문은 N번 실행되므로 시간 복잡도는 O(N).

예제 2: 중첩 반복문

for (int i = 0; i < N; i++) {          // 바깥쪽 반복문
    for (int j = 0; j < N; j++) {      // 안쪽 반복문
        // O(1): 한 번 실행
    }
}

• 안쪽 반복문은 N번 반복, 바깥쪽 반복문도 N번 반복 → 총 실행 횟수는 N×N = N^2.
• 시간 복잡도는 O(N^2).

예제 3: 이진 탐색

int left = 0, right = N - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    // O(1): 한 번 실행
    if (arr[mid] == target) break;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

• 범위가 N, N/2, N/4, ...로 절반씩 줄어듭니다.

총 반복 횟수는 log⁡2N, 시간 복잡도는 O(log⁡N)

 

 

(2) 조건문 확인

조건문 자체는 O(1)이지만, 조건문 안에 다른 연산(반복문 등)이 있는 경우 이를 고려해야 합니다.

예제:

for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
        // O(1): 실행
    } else {
        for (int j = 0; j < N; j++) {
            // O(1): 실행
        }
    }
}

• ii % 2 == 0: 조건문 자체는 상수 시간 O(1)O(1).
• 짝수일 때: O(1) 실행.
• 홀수일 때: 내부 반복문 O(N) 실행.

짝수와 홀수는 NN번 반복되므로 시간 복잡도는 O(N^2)

 

 

(3) 재귀 호출 확인

재귀는 호출 횟수와 각 호출의 연산량을 분석하여 시간 복잡도를 계산합니다.

예제 1: 단순 재귀

void recursive(int n) {
    if (n == 0) return;
    recursive(n - 1);
}

• n이 0이 될 때까지 한 번씩 호출 → 호출 횟수는 n
• 시간 복잡도는 O(N)

예제 2: 분할 정복 재귀

void divideAndConquer(int n) {
    if (n <= 1) return;
    divideAndConquer(n / 2);
    divideAndConquer(n / 2);
}

• 한 번 호출하면 입력이 n→n/2로 줄어들고, 두 번 재귀 호출.
• 호출 트리는 깊이 log N이고, 각 레벨에서 2개의 하위 문제가 생김.
• 총 호출 수는 2^logN=N , 시간 복잡도는 O(N).

 

3. 시간 복잡도 공식 정리

공통 패턴에 따른 시간 복잡도:

 

4. 실제 문제에서 시간 복잡도 계산 예제

문제: 배열에서 두 숫자의 합을 찾기

1. 브루트 포스 (완전 탐색):
   • 바깥 반복문 NN, 안쪽 반복문 N−1N-1 → O(N2)O(N^2).

for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        if (arr[i] + arr[j] == target) {
            return true;
        }
    }
}

 

해시맵을 이용한 최적화:

• 배열 한 번 순회 (O(N)O(N)), HashSet의 삽입/조회는 O(1)O(1) → 전체 시간 복잡도 O(N)O(N).

Set<Integer> set = new HashSet<>();
for (int num : arr) {
    if (set.contains(target - num)) {
        return true;
    }
    set.add(num);
}

 

 

 

5. 시간 복잡도 계산 시 주의점

1. 최악의 경우를 고려: 일반적으로 시간 복잡도는 최악의 경우를 기준으로 계산합니다.
2. 입력 크기 NN의 의미: 문제의 특성에 따라 NN이 달라질 수 있습니다.
   • 예: 그래프 문제에서는 NN이 노드의 개수, 간선의 개수 등이 될 수 있습니다.
3. 상수는 무시: 연산량에 큰 영향을 주지 않는 상수 계수나 낮은 차수는 무시합니다.