[수학] 시간 복잡도

시간 복잡도 계산 및 계층별 정리

1. 시간 복잡도란?

시간 복잡도(Time Complexity) 는 입력 크기 n이 증가할 때, 알고리즘이 수행하는 기본 연산의 횟수를 수학적으로 표현한 것이다.

---

2. 시간 복잡도 계산 방법

2.1 반복문 기준 분석

• 단일 반복문

  for (int i = 0; i < n; i++) { ... } // O(n)
  

• 중첩 반복문

  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) { ... }
  } // O(n^2)
  

• 조건부 반복 (비대칭 반복)

  for (int i = 0; i < n; i++) {
      for (int j = 0; j < i; j++) { ... }
  } // O(n(n-1)/2) => O(n^2)
  

• 로그 반복

  for (int i = 1; i < n; i *= 2) { ... } // O(log n)
  

• 재귀 분할

  T(n) = 2T(n/2) + O(n) // O(n log n)
  

---

3. 시간 복잡도 계층 및 예시

복잡도	설명	대표 예시	해당 예 (예: 위 코드)
O(1)	상수 시간	단순 연산, 배열 접근	없음
O(log n)	로그 시간	이진 탐색	while(l < r) { mid = (l+r)/2; ... }
O(n)	선형 시간	배열 탐색, 단일 반복문	for (int i = 0; i < n; i++)
O(n log n)	로그 정렬	merge sort, quick sort	mergeSort(arr)
O(n^2)	이중 반복문	버블 정렬, 중첩 반복	이중 for문
O(2^n)	지수 시간	부분 집합, 재귀 완전탐색	dfs(pos+1), powerSet()
O(n!)	팩토리얼	순열 생성, TSP	next_permutation, permutation(dfs)

---

4. 실제 비교 (n이 커질수록 차이 커짐)

n	O(1)	O(log n)	O(n)	O(n log n)	O(n^2)	O(2^n)	O(n!)
5	1	2	5	11	25	32	120
10	1	3	10	33	100	1024	3,628,800
20	1	5	20	86	400	1,048,576	약 2.4×10¹⁸

---

5. 위 코드 예시 위치 분석

for (int i = 0; i < n; i++){
    for (int j = 0; j < i; j++){
        a += i + j;
    }
}

• 이 코드는 총 연산 횟수가 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 → O(n^2)

---

6. 참고 정리: 시간 제한과 n의 범위

입력 범위 n	허용 복잡도
n <= 10	O(n!), O(2ⁿ) 가능
n <= 20~25	O(2ⁿ) 가능
n <= 500	O(n³) 이하
n <= 5,000	O(n² log n) 이하
n <= 10⁵	O(n log n) 이하
n <= 10⁷	O(n) 이하
n <= 10⁸	O(1), O(log n)만 가능 (1초 기준)

---

7. 요약

• 시간 복잡도는 입력 크기 n에 대한 연산 횟수 추정이다.
• 대표 복잡도 순서:
  O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
• 위 예시 코드는 O(n^2)에 해당하며, 이중 반복문에서 누적합 형태가 자주 이 복잡도를 유도함.
• 시간 제한과 입력 크기를 고려해 알고리즘을 선택하는 것이 중요하다.