Post

1. 시간복잡도와 공간복잡도

Posted
By noir1458
13 min read
1. 시간복잡도와 공간복잡도

개념

알고리즘의 효율성을 분석하는 방법이다. 입력 크기 N에 따라 연산 횟수(시간)와 메모리 사용량(공간)이 어떻게 증가하는지 표현한다.

  • 시간복잡도: 알고리즘이 수행하는 연산 횟수의 증가율
  • 공간복잡도: 알고리즘이 사용하는 메모리의 증가율
  • 실제 실행 시간이 아닌 증가 추세(Growth Rate)에 집중
  • 하드웨어, 언어에 독립적인 분석 가능

점근적 표기법 (Asymptotic Notation)

표기법의미설명
O (Big-O)상한최악의 경우 (가장 많이 사용)
Ω (Big-Omega)하한최선의 경우
Θ (Big-Theta)상한 = 하한평균적 경우 (정확한 차수)
1
2
3
4
5

예: f(N) = 3N² + 2N + 1

O(N²)  - 최악의 경우 N²에 비례
Ω(N²)  - 최선의 경우도 N²에 비례
Θ(N²)  - 정확히 N² 차수

Big-O 계산 규칙

  1. 상수 제거: O(2N) → O(N)
  2. 낮은 차수 제거: O(N² + N) → O(N²)
  3. 상수는 O(1): O(1000) → O(1)

시간복잡도

주요 복잡도 종류

복잡도명칭N=10N=100N=1000예시
O(1)상수111배열 인덱스 접근
O(log N)로그3710이진 탐색
O(N)선형101001000선형 탐색
O(N log N)선형로그336649966병합/퀵 정렬
O(N²)이차1001000010⁶버블 정렬
O(N³)삼차100010⁶10⁹플로이드-워셜
O(2^N)지수102410³⁰-부분집합
O(N!)팩토리얼10⁶--순열

코테 시간 제한 기준 (1초 기준)

복잡도허용 N 범위
O(N!)N ≤ 10
O(2^N)N ≤ 20~25
O(N³)N ≤ 500
O(N²)N ≤ 5,000~10,000
O(N log N)N ≤ 1,000,000
O(N)N ≤ 10,000,000
O(log N)N ≤ 10¹⁸

분석 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// O(1) - 상수 시간
int getFirst(int arr[], int n) {
    return arr[0];
}

// O(N) - 선형 시간
int sum(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {  // N번
        total += arr[i];            // O(1)
    }
    return total;
}

// O(N²) - 이차 시간
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {       // N번
        for (int j = 0; j < n-1; j++) { // N번
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

// O(log N) - 로그 시간
int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {             // log₂N번
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// O(N log N) - 선형로그 시간
void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);      // T(N/2)
    mergeSort(arr, mid + 1, right); // T(N/2)
    merge(arr, left, mid, right);   // O(N)
}
// T(N) = 2T(N/2) + O(N) = O(N log N)

// O(2^N) - 지수 시간
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

// O(N!) - 팩토리얼 시간
void permutation(int arr[], int depth, int n) {
    if (depth == n) {
        // 순열 하나 완성
        return;
    }
    for (int i = depth; i < n; i++) {
        swap(arr[depth], arr[i]);
        permutation(arr, depth + 1, n);
        swap(arr[depth], arr[i]);
    }
}

복잡한 코드 분석

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 중첩 루프라고 무조건 O(N²)이 아님
void example1(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j += i + 1) {  // i에 따라 반복 횟수 다름
            // ...
        }
    }
}
// 실제: O(N log N) - 조화급수

// 여러 변수가 있는 경우
void example2(int n, int m) {
    for (int i = 0; i < n; i++) {      // O(N)
        for (int j = 0; j < m; j++) {  // O(M)
            // ...
        }
    }
}
// O(N * M) - N과 M 관계 모르면 분리 표기

// 조기 종료가 있는 경우
bool find(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return true;  // 조기 종료
    }
    return false;
}
// 최선: O(1), 최악: O(N), 평균: O(N)

재귀 시간복잡도 (마스터 정리)

T(N) = aT(N/b) + O(N^d) 형태일 때:

조건복잡도
d < log_b(a)O(N^(log_b(a)))
d = log_b(a)O(N^d log N)
d > log_b(a)O(N^d)
1
2
3
4

예: 병합 정렬 T(N) = 2T(N/2) + O(N)
a=2, b=2, d=1
log₂2 = 1 = d
→ O(N log N)

공간복잡도

알고리즘이 사용하는 메모리 공간의 증가율

구성 요소

  1. 고정 공간: 코드, 상수, 변수 (입력 크기와 무관)
  2. 가변 공간: 동적 할당, 재귀 스택 (입력 크기에 비례)

분석 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// O(1) - 상수 공간
int sum(int arr[], int n) {
    int total = 0;  // 변수 1개
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

// O(N) - 선형 공간
int* copyArray(int arr[], int n) {
    int* copy = new int[n];  // N개 공간
    for (int i = 0; i < n; i++) {
        copy[i] = arr[i];
    }
    return copy;
}

// O(N) - 재귀 스택
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 콜스택 N개
}

// O(log N) - 재귀 스택 (이진 탐색)
int binarySearchRecur(int arr[], int left, int right, int target) {
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearchRecur(arr, mid + 1, right, target);
    else
        return binarySearchRecur(arr, left, mid - 1, target);
}
// 콜스택 깊이: log₂N

// O(N²) - 2차원 배열
int** create2DArray(int n) {
    int** arr = new int*[n];
    for (int i = 0; i < n; i++) {
        arr[i] = new int[n];  // 총 N*N 공간
    }
    return arr;
}

시간-공간 트레이드오프

상황시간공간예시
메모이제이션개선증가DP
In-place 정렬유지개선퀵소트
해시 테이블개선증가O(1) 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// 피보나치 - 시간 vs 공간 트레이드오프

// 1. 순수 재귀: O(2^N) 시간, O(N) 공간
int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n-1) + fib1(n-2);
}

// 2. 메모이제이션: O(N) 시간, O(N) 공간
int memo[100] = {0};
int fib2(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib2(n-1) + fib2(n-2);
}

// 3. 타뷸레이션: O(N) 시간, O(N) 공간
int fib3(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 4. 공간 최적화: O(N) 시간, O(1) 공간
int fib4(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

주요 복잡도 비교

증가율 그래프 (N = 1 ~ 100)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

연산 수
    ^
    |                                    O(2^N)
    |                               /
    |                           /
    |                       /
    |                   ___/   O(N²)
    |               ___/
    |           ___/
    |       __--    O(N log N)
    |   __--___----
    |__--___----     O(N)
    |___----_____    O(log N)
    |____________    O(1)
    +-------------------> N

실제 연산 횟수 비교

NO(1)O(log N)O(N)O(N log N)O(N²)O(2^N)
101310331001,024
1001710066410,00010³⁰
1,0001101,0009,96610⁶-
10,00011310,000132,87710⁸-

알고리즘별 복잡도 정리

알고리즘시간 (평균)시간 (최악)공간
이진 탐색O(log N)O(log N)O(1)
버블 정렬O(N²)O(N²)O(1)
병합 정렬O(N log N)O(N log N)O(N)
퀵 정렬O(N log N)O(N²)O(log N)
힙 정렬O(N log N)O(N log N)O(1)
해시 탐색O(1)O(N)O(N)
DFS/BFSO(V + E)O(V + E)O(V)
다익스트라O(E log V)O(E log V)O(V)

면접 포인트

자주 나오는 질문

Q1. O(N)과 O(2N)의 차이는?

차이 없음. Big-O는 상수를 무시하므로 둘 다 O(N)

Q2. 최선/평균/최악 복잡도가 다른 알고리즘 예시?

퀵 정렬: 최선 O(N log N), 평균 O(N log N), 최악 O(N²) 선형 탐색: 최선 O(1), 평균 O(N), 최악 O(N)

Q3. 시간복잡도가 같으면 성능도 같은가?

아니오. O(N)이어도 실제 상수 계수가 다르면 성능 차이 있음 예: 10N vs 1000N 둘 다 O(N)이지만 100배 차이

Q4. 공간복잡도를 줄이는 방법은?

  • In-place 알고리즘 사용 (추가 배열 대신 swap)
  • 재귀 → 반복문 변환 (콜스택 제거)
  • 슬라이딩 윈도우, 투 포인터 활용
  • DP 공간 최적화 (이전 상태만 저장)

Q5. Amortized(분할 상환) 복잡도란?

여러 연산의 평균 시간. 개별 연산은 O(N)일 수 있지만 전체로 보면 O(1) 예: vector push_back - 가끔 O(N) 재할당, 평균 O(1)

코테에서의 활용

1
2
3
4
5
6
7
8
9

// 문제: N이 10만이면 어떤 알고리즘?
// 1초에 약 10⁸ 연산 가정

// N = 100,000
// O(N²) = 10¹⁰ → 시간 초과
// O(N log N) = 1.6 × 10⁶ → 통과
// O(N) = 10⁵ → 통과

// 따라서 O(N log N) 이하 알고리즘 필요

추천 문제

난이도문제링크핵심
Bronze알고리즘 수업 - 알고리즘의 수행 시간 1BOJ 24262O(1)
Bronze알고리즘 수업 - 알고리즘의 수행 시간 2BOJ 24263O(N)
Bronze알고리즘 수업 - 알고리즘의 수행 시간 3BOJ 24264O(N²)
Bronze알고리즘 수업 - 알고리즘의 수행 시간 4BOJ 24265중첩 루프
Bronze알고리즘 수업 - 알고리즘의 수행 시간 5BOJ 24266O(N³)
Bronze알고리즘 수업 - 알고리즘의 수행 시간 6BOJ 24267조합
algorithm
algorithm
This post is licensed under CC BY 4.0 by the author.