코딩테스트-시간복잡도

시간복잡도 (Time Complexity)

시간복잡도란 알고리즘이 얼마나 시간이 걸리는지를 계산하는 척도다. 실제 초 단위 시간이 아니라, 입력 크기(n)에 따라 반복(연산) 횟수가 어떻게 늘어나는지를 중점으로 본다.

---

빅오 표기법 (Big-O)

빅오 표기법은 복잡도를 나타내는 대표 방식으로, 가장 크게 증가하는 항(최고차항)만 남기고 나머지는 생략한다.

2n² + 3n + 100   →   O(n²)

• 계수(2, 3)와 상수(100)는 무시한다.
• n이 커질수록 결국 가장 큰 항이 전체를 지배하기 때문이다.

---

대표 복잡도 읽는 법

• 다항 (n, n², n³ ...) : 중첩된 for문의 개수 = 차수. 이중 포문이면 O(n²), 삼중 포문이면 O(n³).
• 로그 (log n) : 매번 범위가 반으로(또는 일정 비율로) 줄어드는 경우. 밑을 몇 번 곱해 n에 도달하느냐로 결정된다. (예: 이분 탐색)
• 지수 (2ⁿ) : 매 단계마다 경우의 수가 배로 늘어나는 경우. (예: 부분집합 완전탐색)

// O(n) — 반복 1번
for(int i = 0; i < n; i++) { ... }

// O(n²) — 중첩 2번
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++) { ... }

// O(log n) — 매번 절반으로 감소
while(n > 1) { n /= 2; }

---

재귀 함수의 복잡도

재귀 함수의 시간복잡도는 다음처럼 계산한다.

재귀 복잡도 = (함수 호출 횟수) × (호출 1번당 작업량)

즉 메인 로직의 작업량 × 함수가 호출되는 총 횟수다. 예를 들어 호출마다 O(1) 작업을 하고 총 2ⁿ번 호출된다면 전체는 O(2ⁿ)이 된다.

---

정리

• 시간복잡도는 반복 횟수의 증가 추세를 본다.
• 빅오는 최고차항만 남긴다.
• 중첩 for문 개수 = 다항 차수, 절반씩 줄면 log, 배로 늘면 지수.
• 재귀는 호출 횟수 × 호출당 작업량으로 계산한다.