5.1 복잡도

5.1.1 시간 복잡도

• 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 걸리는 연산 횟수를 표현하는 방식
• 보통 빅-오 표기법(Big-O Notation)을 사용하며, 최악의 경우(최악 시간 복잡도)를 기준으로 분석

빅-오 표기법(Big-O Notation)

표기법	의미	예시
O(1)	상수 시간	배열의 특정 원소 접근 (arr[i])
O(log N)	로그 시간	이진 탐색 (std::lower_bound)
O(N)	선형 시간	단순 순회 (std::find)
O(N log N)	로그 선형 시간	퀵 정렬 (std::sort)
O(N^2)	제곱 시간	이중 루프 탐색
O(2^N)	지수 시간	부분 집합 생성

시간 복잡도 예제 (C++ STL)

[벡터 원소 탐색]

#include <iostream>
#include <vector>
#include <algorithm> // std::find 사용

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 특정 원소 탐색 (O(N))
    int target = 7;
    auto it = find(vec.begin(), vec.end(), target);

    if (it != vec.end()) {
        cout << "원소 " << target << "을(를) 찾았습니다. 인덱스: " << distance(vec.begin(), it) << endl;
    } else {
        cout << "원소를 찾을 수 없습니다." << endl;
    }

    return 0;
}

• std::find 함수는 순차 탐색(Linear Search)를 사용하므로 O(N)의 시간 복잡도를 가진다.

---

5.1.2 공간 복잡도

• 공간 복잡도(Space Complexity)는 알고리즘이 사용하는 메모리 양을 의미
• 시간 복잡도와 마찬가지로 빅-오 표기법(Big-O Notation)으로 표현

공간 복잡도 표기법

표기법	의미	예시
O(1)	상수 공간	변수 1~2개 사용
O(N)	선형 공간	크기 N짜리 배열 선언
O(N^2)	제곱 공간	N×N 크기의 2D 배열

공간 복잡도 예제 (C++ STL)

[O(N)의 공간 복잡도, 배열 할당]

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N = 1000000;
    
    // 크기 N인 벡터 생성 (O(N) 공간 사용)
    vector<int> arr(N);

    cout << "배열이 " << arr.size() << "개의 원소를 가지고 있습니다." << endl;

    return 0;
}

• vector<int> arr(N);은 O(N)의 공간을 사용

---

5.1.3 자료 구조에서의 시간 복잡도

[STL 컨테이너별 기본 연산의 시간 복잡도]

자료구조	삽입	삭제	탐색	정렬
vector	O(1) (끝 삽입) / O(N) (중간 삽입)	O(N)	O(N)	O(N log N)
list	O(1) (양 끝)	O(1) (양 끝) / O(N) (중간 삭제)	O(N)	O(N log N)
deque	O(1) (양 끝)	O(1) (양 끝)	O(N)	O(N log N)
set	O(log N)	O(log N)	O(log N)	자동 정렬
unordered_set	O(1) (평균) / O(N) (최악)	O(1) (평균) / O(N) (최악)	O(1) (평균) / O(N) (최악)	자동 정렬 X
map	O(log N)	O(log N)	O(log N)	자동 정렬
unordered_map	O(1) (평균) / O(N) (최악)	O(1) (평균) / O(N) (최악)	O(1) (평균) / O(N) (최악)	자동 정렬 X
priority_queue	O(log N)	O(log N)	O(1) (최댓값 접근)	자동 정렬

 

[set을 이용한 정렬된 삽입과 탐색]

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> s;

    // 삽입 (자동 정렬, O(log N))
    s.insert(10);
    s.insert(5);
    s.insert(20);
    s.insert(15);

    // 탐색 (O(log N))
    if (s.find(10) != s.end()) {
        cout << "10이 존재합니다." << endl;
    }

    // 정렬된 상태로 출력
    for (int x : s) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

 

 

10이 존재합니다.
5 10 15 20

• set은 내부적으로 이진 탐색 트리(BST, Red-Black Tree)를 사용, O(log N) 시간 복잡도