1. 알고리즘 복잡도란
알고리즘 복잡도는 계산 수행의 어려움에 대한 측정치 — 알고리즘이 문제를 해결하는 데 필요한 자원(시간 및 공간)의 양을 비용 관점에서 나타낸다.
식당의 레시피 복잡도는 두 가지로 측정할 수 있다.
- 시간 복잡도: 요리 하나 만드는 데 얼마나 걸리나?
- 공간 복잡도: 필요한 재료·도구는 얼마나 많은가?
좋은 레시피는 짧은 시간 + 적은 재료로 맛있는 요리를 만든다.
| 시간 복잡도 | 연산 수, 단계 수 | 횟수 |
| 공간 복잡도 | 메모리 사용량 | 비트, 바이트 |
💡 핵심 통찰: 알고리즘 복잡도는 "입력 크기 n에 따른 함수"로 표현된다. 데이터가 2배 늘어났을 때 시간이 2배 늘어나는지, 4배 늘어나는지, 100만 배 늘어나는지가 핵심이다.
2. 시간 복잡도 (Time Complexity) ⭐⭐⭐
알고리즘이 작업을 수행하는 데 필요한 연산 또는 단계의 총 수를 나타내는 측정치.
| "10초 걸린다" | "10번의 비교 연산이 필요하다" |
| "내 컴퓨터에서 5초" | "n개 입력에 대해 n번 연산" |
| 실제 시간 (초) | 컴퓨터 성능마다 다름 |
| 실제 시간 (초) | 프로그래밍 언어마다 다름 |
| 실제 시간 (초) | 같은 코드도 매번 다른 결과 |
| 연산 횟수 | 모든 환경에서 일관됨 ✅ |
💡 알고리즘 자체의 본질적 효율성만 평가하려면 시스템에 의존하지 않는 척도가 필요하다. 그것이 연산 횟수다.
3. 시간 복잡도 계산 — find_maximum 예제 ⭐
19강에서 봤던 최댓값 찾기 알고리즘으로 시간 복잡도 계산법을 익혀보자.
procedure find_maximum
max := a₁ {t₁: 1번 수행}
for i := 2 to n {t₂: n번 반복}
if aᵢ > max then max := aᵢ {t₃: 최악의 경우 n-1번 갱신}
return max {t₄: 1번 수행}| max := a₁ | t₁ | 1 | t₁ |
| for i := 2 to n | t₂ | n | n · t₂ |
| if aᵢ > max then... | t₃ | n−1 (최악) | (n−1) · t₃ |
| return max | t₄ | 1 | t₄ |
T(n) = t₁ + n · t₂ + (n−1) · t₃ + t₄
여기서 t₁, t₂, t₃, t₄는 각 연산에 걸리는 상수 시간이다.
💡 시험 풀이 핵심: 시간 복잡도 계산은 각 명령어에 시간을 할당하고, 수행 횟수를 곱한 후 합산하는 표준 절차를 따른다. 이 절차만 익히면 어떤 의사코드든 분석 가능하다.
4. 공간 복잡도 (Space Complexity)
알고리즘이 계산을 수행하는 데 필요한 메모리 비트의 총 수를 나타내는 측정치.
요리사가 음식을 만들 때 필요한 도마, 냄비, 그릇 등의 크기와 개수.
| 임베디드 시스템 | 메모리가 제한된 환경 |
| 모바일 앱 | 기기 호환성, 배터리 소모 |
| 빅데이터 처리 | 메모리 부족 방지 |
| 클라우드 비용 | 메모리 사용량 = 비용 |
알고리즘 설계에서 시간을 빠르게 하면 공간이 더 들고, 공간을 아끼면 시간이 더 걸리는 경우가 많다.
예: 캐싱(공간 많이 써서 시간 단축), 압축(공간 아끼고 시간 더 씀)
💡 시험 핵심: 시험에서 "시간 복잡도"만 묻는 경우가 90%지만, 공간 복잡도 개념도 정확히 알아야 한다. 두 척도 모두 알고리즘 평가의 두 축이다.
5. 성장률 (Order of Growth) ⭐⭐⭐ 핵심 중의 핵심
입력 크기 n이 무한히 커질 때 알고리즘의 시간 T(n)이 어떻게 증가하는지를 나타내는 척도. 최고차항만 남기고 상수와 낮은 차수의 항은 무시.
자동차의 성능을 나타낼 때 세부적인 가속력, 연비를 일일이 따지지 않고 "최고 시속 200km" 처럼 핵심 지표만 본다. 알고리즘도 마찬가지로 가장 지배적인 항만 본다.
| ① 최고차항만 남김 | 가장 빠르게 증가하는 항만 |
| ② 상수 계수 무시 | 3n²와 100n²는 동일하게 O(n²) |
| ③ 점근적 분석 | n → ∞일 때의 동작만 본다 |
T(n) = 3n² + 5n + 10이라면?
| 3n² | 최고차항, 상수 무시 | n² |
| 5n | 낮은 차수, 무시 | n |
| 10 | 상수, 무시 | 1 |
→ 성장률: O(n²) ✅
T(n) = t₁ + n · t₂ + (n−1) · t₃ + t₄
| t₁ | 상수 | Θ(1) |
| n · t₂ | n에 비례 | Θ(n) |
| (n−1) · t₃ | n에 비례 | Θ(n) |
| t₄ | 상수 | Θ(1) |
→ 합치면 Θ(1) + Θ(n) + Θ(n) + Θ(1) = Θ(n) ✅
6. 점근적 표기법 (Asymptotic Notation) ⭐
성장률을 표현하는 3가지 표준 표기법.
| O(f(n)) | 빅 오 (Big-O) | 상한선 (최악의 경우 이하) |
| Ω(f(n)) | 빅 오메가 (Big-Ω) | 하한선 (최선의 경우 이상) |
| Θ(f(n)) | 빅 세타 (Big-Θ) | 정확한 경계 (상한·하한 모두) |
┌───── O(f(n)) ← 절대 이보다 느려지지 않음 (상한)
│
T(n) │ ← 실제 알고리즘 성능
│
└───── Ω(f(n)) ← 절대 이보다 빨라지지 않음 (하한)
Θ(f(n)) = 상한·하한 모두 같을 때시험에서는 빅 오(O) 표기가 가장 자주 사용된다. "최악의 경우 시간 복잡도" 를 의미하기 때문이다.
💡 시험 핵심: 일상에서 "이 알고리즘은 O(n²)이다"라고 말하면, 실제로는 "최악의 경우 n²에 비례한다" 는 의미. 엄밀히는 Θ가 정확한 표현이지만 관습적으로 O를 더 자주 쓴다.
7. Big-O의 엄밀한 수학적 정의 ⭐⭐⭐⭐ ★ 신규 보강
지금까지 Big-O를 직관적으로 이해했지만, 시험에서는 엄밀한 수학적 정의를 묻는 경우가 있다. 교수님 원래 교안 p.6~7에서 강조된 표준 정의를 정리한다.
f(x) = O(g(x)) ⟺ ∃ 상수 C > 0, 상수 k 가 존재하여, 모든 x > k 에 대해 |f(x)| ≤ C|g(x)|
| ∃ C | 어떤 양의 상수 C가 존재 |
| ∃ k | 어떤 임계점 k가 존재 |
| ∀ x > k | k보다 큰 모든 x에 대해 |
| |f(x)| ≤ C|g(x)| | f(x)의 절댓값이 C 곱하기 g(x) 절댓값 이하 |
"충분히 큰 x (k보다 큰 x)에 대해, f(x)는 g(x)에 상수 배(C) 만큼만 떨어진다."
즉, f(x)의 증가율이 g(x)의 증가율보다 빠르지 않다.
"이 자동차는 최대 시속 100km/h이다" 라는 말은, 이 차가 100km/h를 넘을 수 없다는 의미이지 항상 100km/h로 달린다는 뜻은 아니다.
마찬가지로 f(x) = O(g(x))는 f(x)가 g(x)의 상수 배보다 빨리 증가할 수 없다는 뜻이다.
| 1. C와 k는 유일하지 않음 | 정의를 만족하는 어떤 (C, k) 쌍이라도 찾으면 OK |
| 2. 충분히 큰 x | 작은 x에서는 부등식이 안 성립해도 됨 |
| 3. 절댓값 사용 | 음수 함수도 다룰 수 있도록 |
8. Big-O 증명 절차 — 표준 4단계 ★ 신규 보강
| 1 | f(x) ≤ C · g(x) 형태로 변형 시도 |
| 2 | 적절한 C 값 선택 |
| 3 | 그 C에 대해 부등식이 성립하는 k 값 찾기 |
| 4 | 모든 x > k에서 부등식 성립 확인 |
30n + 8 ≤ C · n 을 만족하는 C, k 찾기
30n + 8 ≤ Cn 8 ≤ (C − 30)n n ≥ 8/(C − 30) (단, C > 30)
C = 31 로 두면, 8 ≤ (31 − 30)n = n → n ≥ 8
k = 8
모든 n > 8에 대해 30n + 8 ≤ 31n 성립 ✅
C = 31, k = 8일 때 30n + 8 ≤ 31n 이 모든 n > 8에 대해 성립
따라서 30n + 8 = O(n) ✅
| 합 규칙 | f₁ = O(g₁), f₂ = O(g₂) ⟹ f₁ + f₂ = O(max(g₁, g₂)) |
| 곱 규칙 | f₁ = O(g₁), f₂ = O(g₂) ⟹ f₁ · f₂ = O(g₁ · g₂) |
| 다항식 규칙 | 차수 d 다항식 = O(nᵈ) |
💡 시험 함정: f(x) = O(g(x))가 "f(x)와 g(x)가 같다"는 뜻이 아니다. 단지 f(x)가 g(x)보다 빠르게 증가하지 않는다는 상한의 의미다. 예를 들어 n = O(n²)도 참이다.
9. 주요 성장률 종류 — 빠른 것부터 느린 것까지 ⭐⭐⭐
알고리즘 분석에서 자주 등장하는 성장률을 빠른 순서로 정리.
| O(1) | 상수 시간 | 1 | 배열 인덱스 접근 |
| O(log n) | 로그 시간 | ~10 | 이진 탐색 |
| O(n) | 선형 시간 | 1,000 | 선형 탐색 |
| O(n log n) | 선형 로그 시간 | ~10,000 | 병합 정렬, 퀵 정렬 |
| O(n²) | 이차 시간 | 1,000,000 | 버블 정렬, 삽입 정렬 |
| O(n³) | 삼차 시간 | 10⁹ | 행렬 곱셈 (단순) |
| O(2ⁿ) | 지수 시간 | 천문학적 | 부분집합 탐색 |
| O(n!) | 팩토리얼 시간 | 우주 시간 초과 | 외판원 문제 |
실행 시간
│ O(2ⁿ)
│ O(n²)/
│ /
│ O(n log n)
│ /
│ O(n)
│ /
│ O(log n)
│
│ O(1)
└────────────────────────────────── 입력 크기 n| O(1) | 1번 | 즉시 |
| O(log n) | ~20번 | 즉시 |
| O(n) | 1,000,000번 | 1초 |
| O(n log n) | ~2,000만 번 | 20초 |
| O(n²) | 1조 번 | 약 11일 |
| O(2ⁿ) | 2¹⁰⁰⁰⁰⁰⁰ | 우주의 나이 초과 |
💡 충격 사실: O(n²)와 O(n log n)의 차이는 보기엔 작아 보이지만, 100만 데이터에서 20초 vs 11일의 차이가 난다. 이것이 실무에서 알고리즘 선택이 중요한 이유다.
10. 작은 입력의 함정 ⚠️
성장률은 n이 충분히 커진 상태에서의 동작을 본다. 작은 n에서는 O(n²)가 O(n)보다 빠를 수도 있다.
알고리즘 A: T_A(n) = 100n + 500 → O(n) 알고리즘 B: T_B(n) = 2n² + 10 → O(n²)
| 10 | 1,500 | 210 | B (O(n²))이 빠름 |
| 100 | 10,500 | 20,010 | A가 빠름 |
| 1,000 | 100,500 | 2,000,010 | A 압도적 |
| 10,000 | 1,000,500 | 200,000,010 | A 절대 압승 |
| 작은 n | 상수도 중요 |
| 큰 n | 성장률만 중요 |
💡 실전 적용: 작은 데이터에서는 O(n²) 알고리즘이 더 빠를 수 있어, "작은 정렬은 삽입 정렬 사용" 같은 최적화가 실무에 존재한다 (Timsort가 대표적).
11. 최악의 경우 (Worst-Case) 분석 ⭐
알고리즘이 '가장 운이 나쁠 때' 의 성능을 분석하는 방법. 즉, 가장 비효율적인 입력에 대한 성능.
자동차의 안전성을 평가할 때 가장 극한의 충돌 환경에서 테스트한다. 알고리즘도 마찬가지로 최악의 시나리오를 가정.
| 성능 보장 | 하한선 보장 (이보다 느려지지 않음) |
| 안정성 | 예상치 못한 부하에서도 작동 |
| 실무 의존성 | 실시간 시스템·금융·의료 등 필수 |
| 최선의 경우 (Best) | 가장 운이 좋을 때 | 거의 안 씀 |
| 평균의 경우 (Average) | 확률적 평균 | 가끔 씀 |
| 최악의 경우 (Worst) | 가장 운이 나쁠 때 | 표준 사용 ⭐ |
"if aᵢ > max then max := aᵢ"가 매번 참이 되어 max 갱신이 매번 발생할 때.
→ 배열이 오름차순으로 정렬되어 있을 때 (각 단계마다 새 최댓값 발견)
💡 시험 핵심: 알고리즘 복잡도 문제에서 별다른 명시가 없으면 항상 최악의 경우 분석으로 답한다.
12. 선형 탐색의 시간 복잡도 분석 ⭐
19강에서 배운 선형 탐색을 복잡도 관점에서 다시 보자.
| 최선 | 첫 번째에서 발견 | O(1) |
| 평균 | 중간쯤에서 발견 | O(n/2) ≈ O(n) |
| 최악 | 마지막에서 발견 또는 없음 | O(n) |
선형 탐색의 시간 복잡도 = O(n) (최악의 경우 기준)
13. 이진 탐색의 시간 복잡도 분석 ⭐⭐⭐
이진 탐색 = O(log n)
데이터 개수가 n = 2ᵏ일 때, 이진 탐색은 검색 범위를 매번 절반으로 축소한다.
| 시작 | 2ᵏ = n |
| 1단계 | 2ᵏ⁻¹ = n/2 |
| 2단계 | 2ᵏ⁻² = n/4 |
| 3단계 | 2ᵏ⁻³ = n/8 |
| ... | ... |
| k단계 | 2⁰ = 1 (찾음 또는 종료) |
→ 총 k번 반복 후 종료
n = 2ᵏ → 양변에 log₂를 취하면: log₂(n) = log₂(2ᵏ) = k
→ k = log₂(n)
따라서 시간 복잡도는 Θ(log n) ✅
💡 n이 2의 거듭제곱이 아니어도 이 성질은 성립한다. 약간 더 복잡한 분석이 필요하지만 결론은 같다: Θ(log n).
| 1,000 | ~10번 |
| 100만 | ~20번 |
| 10억 | ~30번 |
| 1조 | ~40번 |
💡 놀라운 사실: 데이터가 1000배 늘어나도 비교 횟수는 단 10번 늘어난다. 로그 함수의 위력이며, 이진 탐색이 대용량 데이터의 절대 강자인 이유다.
14. 정렬 알고리즘 복잡도 종합 비교 ⭐
| 버블 정렬 | Θ(n²) | Θ(n²) | 단순, 비효율 |
| 삽입 정렬 | Θ(n²) | Θ(n²) | 거의 정렬된 데이터에 효율적 |
| 병합 정렬 | Θ(n log n) | Θ(n log n) | 안정적, 추가 메모리 필요 |
| 힙 정렬 | Θ(n log n) | Θ(n log n) | 메모리 효율적 |
| 퀵 정렬 | Θ(n²) ⚠️ | Θ(n log n) | 평균 매우 빠름 |
| 카운팅 정렬 | Θ(n) | Θ(n) | 정수 한정, 범위 제약 |
| 기수 정렬 | Θ(n) | Θ(n) | 정수·문자열 한정 |
| 팀 정렬 | Θ(n log n) | Θ(n log n) | Python·Java 표준 |
| O(n²) — 단순 | 버블, 삽입, 선택 |
| O(n log n) — 효율 | 병합, 힙, 퀵(평균), 팀 |
| O(n) — 특수 조건 | 카운팅, 기수 |
💡 시험 핵심 함정: "모든 정렬이 O(n²) 라고 답하면 큰 실수다. 단순 비교 정렬만 O(n²)이고, 고급 정렬은 O(n log n), 특수 조건에서는 O(n) 정렬도 가능하다.
💡 퀵 정렬의 함정: 퀵 정렬은 평균 O(n log n)이지만 최악의 경우 O(n²) 이다. 피벗 선택을 잘못하면 (예: 이미 정렬된 데이터) 성능이 폭락한다. 실무에서는 랜덤 피벗이나 메디안-오브-쓰리(median-of-three)로 이 함정을 피한다.
15. Tractable vs Intractable — 풀 수 있는 문제와 풀기 어려운 문제 ★ 신규 보강
복잡도는 단순한 성능 측정을 넘어 문제 자체의 본질적 난이도를 분류하는 기준이 된다.
| Tractable (풀만한 문제) | 다항 시간(Θ(nᶜ))으로 해결 가능한 문제 |
| Intractable (풀기 어려운 문제) | 다항 시간 이상(지수, 팩토리얼 등) 걸리는 문제 |
P (Polynomial): 모든 Tractable 문제의 집합
| Tractable (P) | 정렬, 최단 경로(다익스트라), 두 수의 곱셈 |
| Intractable | 외판원 문제(O(n!)), 부분집합 합 문제 |
| 이론적 Tractable | n^1,000,000도 다항식이지만 실용적으로는 불가능 |
| 이론적 Intractable | c^(loglog n) 같은 비다항식도 실제로는 빠를 수 있음 |
💡 시험 핵심: "Tractable"의 기준은 다항 시간 내 해결 가능성이다. 다항 시간 알고리즘이 발견되면 실용적으로 처리 가능하다고 본다.
일부 문제는 어떤 알고리즘으로도 해결 불가능하다. 1930년대 앨런 튜링이 증명했다.
대표 예시: 정지 문제(Halting Problem) — 임의의 알고리즘과 입력이 주어졌을 때, 그 알고리즘이 정지할지 무한 루프에 빠질지 판단하는 일반적 알고리즘은 존재하지 않는다.
💡 특별편 3에서 자세히: P vs NP 문제, 정지 문제의 자세한 내용은 특별편 3에서 다룬다. 시험에서는 분류 자체를 묻는 경우가 많다.
16. 복잡도 분석의 실전 활용
입력 크기 n과 알고리즘 복잡도를 알면, 실행 시간을 대략 예측할 수 있다.
| n ≤ 10 | O(n!) 가능 (브루트포스) |
| n ≤ 25 | O(2ⁿ) 가능 (지수 탐색) |
| n ≤ 5,000 | O(n²) 가능 |
| n ≤ 1,000,000 | O(n log n) 권장 |
| n > 1,000,000 | O(n) 또는 O(log n) 필수 |
"1초 안에 풀 수 있는 연산 수 ≈ 1억 번"
이 기준으로 알고리즘을 선택하면 시간 초과를 피할 수 있다.
| 100 | O(n³) |
| 1,000 | O(n²) |
| 100,000 | O(n log n) |
| 10,000,000 | O(n) |
💡 개발자 실무 직결: 복잡도 분석은 단순 시험 도구가 아니다. 모든 코딩테스트와 실무 시스템 설계의 핵심이다. 알고리즘 선택의 가장 중요한 기준.
📌 한눈에 보는 핵심정리
| 알고리즘 복잡도 | 시간(연산 수) + 공간(메모리) 측정 |
| 시간 복잡도 | 연산 수, "초"가 아닌 횟수 |
| 공간 복잡도 | 메모리 비트 수 |
| 성장률 | n→∞일 때 최고차항만 남기기 |
| 성장률 3원칙 | 최고차항만, 상수 무시, 점근적 |
| 빅 O (O) | 상한선 (최악의 경우) |
| 빅 오메가 (Ω) | 하한선 |
| 빅 세타 (Θ) | 정확한 경계 |
| Big-O 엄밀 정의 ⭐ | ∃C, k: |f(x)| ≤ C|g(x)| (∀x > k) |
| 주요 성장률 | O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) |
| 최악의 경우 분석 | 표준 분석 방식 |
| 선형 탐색 | O(n) (최악) |
| 이진 탐색 | O(log n) (정렬 필수) |
| 단순 정렬 | O(n²) (버블, 삽입) |
| 고급 정렬 | O(n log n) (병합, 힙) |
| Tractable / Intractable ⭐ | 다항 시간 가능 / 불가능 |
🧠 예상문제 2제
문제 1. 시간 복잡도 계산
다음 의사코드의 시간 복잡도(빅 오 표기)로 옳은 것은?
procedure example(n: integer)
sum := 0
for i := 1 to n
for j := 1 to n
sum := sum + i * j
return sum① O(n) ② O(n log n) ③ O(n²) ④ O(n³)
👉 정답: ③
| sum := 0 | 1 |
| 외부 for (i := 1 to n) | n |
| 내부 for (j := 1 to n) | n (각 i에 대해) |
| sum := sum + i * j | n × n = n² |
| return sum | 1 |
T(n) = 1 + n² + 1 = n² + 2
최고차항: n² → O(n²) ✅
💡 시험 핵심 패턴: 이중 for 반복문은 O(n²) 의 시그니처다. 외부 루프 n번 × 내부 루프 n번 = n²번 실행. 마찬가지로 삼중 for는 O(n³).
문제 2. Big-O 정의에 따른 증명 (신규 보강)
다음 함수가 O(n²)임을 정의에 따라 증명하시오.
f(n) = 2n² + 5n + 3
2n² + 5n + 3 ≤ C · n² 을 만족하는 C, k 찾기
n ≥ 1일 때 5n ≤ 5n², 3 ≤ 3n² 이므로:
2n² + 5n + 3 ≤ 2n² + 5n² + 3n² = 10n²
C = 10, k = 1 일 때 모든 n > 1에 대해 2n² + 5n + 3 ≤ 10n² 성립
따라서 f(n) = O(n²) ✅
| 1 | 10 | 10 | = (성립) |
| 2 | 21 | 40 | ✅ |
| 5 | 78 | 250 | ✅ |
| 100 | 20,503 | 100,000 | ✅ |
💡 추가 학습 — Big-O 증명 노하우:
- C는 가능한 큰 값으로 잡는 게 안전 (정의를 만족하기 쉬움)
- k는 가능한 작은 값부터 시작
- 다항식의 경우 최고차항만 남기고 나머지는 모두 최고차항으로 흡수시키는 게 표준 트릭
- C와 k는 유일한 답이 없음. 정의를 만족하는 어떤 쌍이라도 OK
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-21] 정수론 기초 — 나누어떨어짐·mod·진법 변환 (1) | 2026.06.15 |
|---|---|
| [이산구조 특별편 3] 컴퓨터가 풀 수 없는 문제 — P vs NP와 튜링의 정지 문제 (0) | 2026.06.14 |
| [이산구조 개념-19] 검색·정렬·탐욕 알고리즘 — 5가지 핵심 알고리즘 (0) | 2026.06.12 |
| [이산구조 개념-18] 알고리즘의 기초 — 정의·6대 특징·의사코드 (0) | 2026.06.11 |
| [이산구조 개념-17] 영-일 행렬과 부울린 연산 — 0과 1로 그리는 관계의 지도 (0) | 2026.06.10 |