시간복잡도(time complexity)

시간복잡도란?

어떤 알고리즘이 입력 크기 N에 따라
얼마나 많은 연산을 수행하는지를 수학적으로 표현한 것임

즉 -> 입력이 커지면 , 이 코드가 얼마나 느려질까를 예측하는 기준

예시 :

for (int i = 0; i < N; i++) {
    printf("%d\n", i);
}

N번 반복하니까 -> 시간복잡도는 O(N)

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        printf("%d %d\n", i, j);
    }
}

N * N번 반복하니까 -> 시간복잡도는 O(N²)

O(..)식으로 쓰는 이유

이건 빅오(Big-O)표기법이라고 부르는데
"입력이 무한히 커질 때, 가장 영향이 큰 항만 남긴 것"

예시 :

int cnt = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        cnt++;
    }
}
printf("끝!\n");

cnt++ → 이건 N * N번 실행됨
printf("끝!\n"); → 딱 한 번 실행됨
정확히 따지면 전체 연산 횟수 = N² + 1(여기서 1은 printf 한번으로 쳐줌)
근데 왜 1은 무시하냐

빅오 표기법은 "입력값이 매우 커질 때"를 기준으로 함
-> N = 1000이면 N² = 1,000,000
근데 +1 해봤자 1,000,001임
무의미한 수준이라서 상수항을 그냥 떼버림

시간복잡도가 중요한 이유

1. 시간초과를 피하려면 반드시 필요함

-코딩테스트
-백준
-정올
대부분의 문제는 시간 제한이 1초 or 2초임
이 시간 안에 코드가 입력 데이터를 다 처리해야함

그래서

"내 코드가 시간 안에 끝날 수 있을까?"를 미리 예측할 수 있어야함

실전 표 :

시간복잡도	입력 N 크기 제한 (안전선)
O(1)	무조건 됨
O(N)	N ≤ 1e8 정도까지
O(N log N)	N ≤ 1e6 ~ 1e7까지도 가능
O(N²)	N ≤ 2000 ~ 5000 (상황 따라 다름)
O(2^N)	N ≤ 20 미만만 가능

2. 객관적으로 비교 가능함

두 개 코드가 다 맞는다고 해도
하나는 O(N²)
하나는 O(N log N)이라면

-> 큰 입력에서 성능차이가 큼
예 :
N = 1000000일 때
O(N²) -> 몇조번 연산 -> 터짐
O(N log N) -> 2천만번 수준 -> 통과

3. 알고리즘 선택 기준이 됨

문제마다 어떤 알고리즘을 써야 하는지 감 잡는 기준이 됨

시간복잡도	대표 알고리즘 예시
O(1)	해시, 딕셔너리 조회 등
O(N)	단순 for문, 누적합, 투포인터
O(N log N)	정렬, 우선순위큐, 세그트리 등
O(N²)	완전탐색, 이중 for문
O(2^N)	백트래킹, 모든 조합/부분집합
O(N!)	순열 다 돌기 (매우 위험ㅋㅋ)

알고리즘 문제를 풀기 위한 눈을 기른다랄까..

그럼 언제, 어떻게 시간 복잡도를 직접 계산하냐

1. 문제 입력 범위를 보기

대부분의 문제는 입력 범위 = 시간복잡도 힌트임
| 입력 범위 (N) | 가능한 시간복잡도 | 설명 |
| --------------- | ------------------ | ------------------- |
| N ≤ 10 | O(N!), O(2^N) 가능 | 완전탐색, 순열 다 돌려도 됨 |
| N ≤ 1000 | O(N²) 가능 | 이중 for문 OK |
| N ≤ 100,000 | O(N log N) 이하 필요 | 정렬, 이분탐색, 투포인터 등 |
| N ≤ 1,000,000 | O(N)만 가능 | for문 딱 한 번 수준 |
| N ≤ 1e9~1e18 | O(log N), O(1)만 가능 | 수학적 처리, 이진 탐색 등만 가능 |

참고 : 1e9같은 표현은 프밍에서 자주 쓰이는 지수 표기법(scientific notation)임
1e3 → 1 10^3 = 1000
1e6 → 1 10^6 = 1,000,000
C언어에서 실수 자료형에서도 쓸 수 있음

double a = 1e9; // 10억
printf("%.0f\n", a); // 1000000000 출력

2. "내 코드가 몇번 반복되냐" 스스로 세보면 됨

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        // ...
    }
}

반복 횟수 = N² → O(N²)

3. "최악의 상황"을 기준으로 잡아야 함

if (a == 1) return;
else for (int i = 0; i < N; i++) doSomething();

여기서 최악의 경우는 a == 1일 때의 O(1) 이 아니고
a != 1 일ㄷ 때의 O(N)임
-> 그러면 시간복잡도는 O(N)이라고 표현함

실전 시간복잡도 예측해보기

예제 2번: N ≤ 100,000일 때
문제 예시:
"N개의 수가 주어지고, 두 수의 차이가 특정 조건을 만족해야 한다. 조건을 만족하는 쌍의 개수를 구하라."
입력: 3 5 8 10 14
조건: 두 수의 차이가 5 이상인 경우 쌍으로 센다

가장 단순한 방법 : 완전탐색

for (int i = 0; i < N; i++) {
    for (int j = i+1; j < N; j++) {
        if (abs(arr[i] - arr[j]) >= K) count++;
    }
}

이중 for문 -> O(N²)
N이 최대 100,000이라면?
연산 횟수 : 100,000² = 100억 번 → 1초 안에 못 끝남
왜냐? :
온라인 채점 시스템 기준으로는
"1초에 약 1억 번 연산 가능" 이라고 알려져 있음
즉 -> 1초 ≈ 10⁸번 연산 가능

N = 100,000;
for (int i = 0; i < N; i++) doSomething();

약 100,000번 → 1초에 충분히 가능

N = 100,000;
for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) {
    doSomething();
  }
}

100,000 * 100,000 = 10,000,000,000 (100억)
1억 x 100초 필요 -> 불가능