1. 기본개념 - 시간복잡도 & 공간복잡도

시간복잡도와 공간복잡도

프로그래밍에서 알고리즘의 효율성을 판단할 때 가장 기본이 되는 개념

• 시간복잡도(Time Complexity) :  코드가 얼마나 오래 걸리는가
• 공간복잡도(Space Complexity) : 코드가 얼마나 많은 메모리를 쓰는가

---

- 시간복잡도 (Time Complexity)

시간복잡도는 입력 크기 n이 커질 때, 알고리즘이 실행되는 데 걸리는 시간의 증가 정도를 표현함.
정확한 시간을 재는 게 아니라, 성장 속도(증가율) 를 비교하는 개념

 

** Big-O, Big-Ω, Big-Θ

알고리즘의 효율성을 분석할 때는 시간복잡도나 공간복잡도를 입력 크기 n에 대한 함수 형태로 표현함.
이때 “얼마나 빨리 증가하는가”를 수학적으로 나타내는 게 바로 점근적 표기법(Asymptotic Notation) 이다.

 

대표적으로 세 가지가 있음:

Big-O (빅오) **	Big-Ω (빅오메가)	Big-Θ (빅세타)
최악의 경우 (Upper bound)	최선의 경우 (Lower bound)	평균적 혹은 정확한 경우 (Tight bound)
알고리즘이 아무리 잘 안 풀려도  이 정도 시간 이상은 걸리지 않는다는 상한선	“운이 정말 좋을 때는 이 정도만 걸린다”는 하한선	입력 크기가 커질 때 실제 복잡도가  특정 함수와 거의 같은 속도로 증가할 때 사용
검색이 끝까지 안 될 때	검색이 처음에 성공할 때	“이 알고리즘의 실제 복잡도가 정확히 이 정도 수준”이라는 의미로, 상한(O)과 하한(Ω)이 같을 때 쓴다.

 

 

예를 들면

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

• 항상 n번 반복하므로 O(n), Ω(n), Θ(n)
• 어떤 입력이 들어와도 n번 수행함 → 최악, 최선이 같음

다음 예시를 보면 의미가 더 분명해짐:

for (int i = 0; i < n; i++) {
    if (arr[i] == x) break;
}

• 최선: 첫 번째 원소가 x → 1번만 실행 Ω(1)
• 최악: x가 없거나 마지막에 있음 → n번 실행 O(n)

시간복잡도 표기 시 보통 Big-O를 주로 사용함.

대표적으로 아래와 같이 사용

O(1)	O(log n)	O(n log n)
상수 시간 → 입력 크기와 상관없이 항상 일정한 시간	로그 시간 → 데이터가 커질수록 조금씩만 증가 (이진 탐색 등)	로그를 곱한 선형 시간 (병합 정렬, 퀵 정렬 평균 등)
O(n)	O(n²)	O(2ⁿ)
선형 시간 → 데이터 개수만큼 반복	제곱 시간 (중첩 반복문)	지수 시간 (모든 경우 탐색, 완전탐색 등)

 

- 코드로 시간복잡도 계산하는 법

// 1. 입력 크기와 상관없이 한 번만 실행 → O(1)
if (n > 100) cout << "big";
else cout << "small";

// 2. 반복문이 n번 실행 → O(n)
for (int i = 0; i < n; i++) {cout << i << endl;}

// 3. 바깥 루프 n번 × 안쪽 루프 n번 = n × n = O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << " " << j << endl;
    }
} 

// 4. O(log n)
for (int i = 1; i < n; i *= 2) {
    cout << i << endl;
} //→ i가 1, 2, 4, 8, … 식으로 2배씩 증가 → 약 log₂(n)번 반복 → O(log n)


// 5. O(n log n)
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        cout << i << " " << j << endl;
    }
} // → 바깥 루프: n번, 안쪽 루프: log n번 → 총 O(n log n)

// 6. 재귀는 호출 횟수 × 각 호출의 비용으로 계산

• 상수나 작은 항은 무시 (O(2n) → O(n))
• 가장 큰 항만 남김 (O(n² + n) → O(n²))

---

- 공간복잡도 (Space Complexity)

공간복잡도는 알고리즘이 실행되는 동안 필요로 하는 메모리의 양을 나타냄.
입력 크기 n에 따라 필요한 추가 메모리의 증가율을 본다.

 

예를 들어,

int sum = 0;          // 상수 공간
int arr[n];           // 입력 크기 n에 비례하는 공간

• sum은 1개의 변수만 필요 → O(1)
• arr은 n개의 정수 저장 → O(n)