알고리즘 분석(계산 복잡도)Algorithm Analysis and Computational Complexity
알고리즘에서 절차의 시간 · 공간 비용을 입력 크기로 세고, 그 비용이 다항인지 지수인지로 문제의 어려움을 가르는 일이다. 평균 비용을 셈하는 확률과 근사 해의 반복 횟수를 다루는 수치 해석을 도구로 함께 둔다.
1요약
- 알고리즘 분석은 알고리즘 가운데 비용을 세고 문제의 어려움을 가르는 갈래로, 시간 복잡도(Big-O) · P · NP 문제 · 확률 · 베이즈 정리 · 수치 해석 네 토픽이 자료구조 · 설계 기법 · 그래프 알고리즘의 절차를 같은 잣대로 잰다.
- 비용을 세지 않으면 «더 빠른 기계»가 답처럼 보인다 — 부분집합 합 전수 탐색은 초당 10⁹ 번 연산(가정 값)에서 1초 안 n = 25 이고, 기계를 10배로 늘려도 n = 28 에 그친다(원문 식 직접 계산 · 그림 5).
- 「입력이 조금 늘었는데 너무 느려졌다」는 n 을 1 늘릴 때의 시간 비로 가른다 — 비가 2 근처에서 일정하면 지수 탐색(P · NP 문제), 비가 1 로 다가가면 다항 비용(시간 복잡도), 같은 n 에서 실행마다 크게 갈리면 입력 분포(확률) 쪽이다.
2등장 배경
기계가 빨라지면 어떤 문제든 풀리리라 여겼지만, 조합을 모두 시도하는 절차는 입력이 하나 늘 때마다 시간이 배로 늘어 기계 개선을 삼켰다. von Neumann 은 1953년에 이미 다항 시간과 지수 시간 알고리즘을 구별했다(Cook P vs NP 설명서 2절).
1960년대 Cobham 과 Edmonds 가 다항 시간 계산을 정의했고 Edmonds 는 이를 «좋은 알고리즘»이라 불렀다. Cook 은 1971년 충족 가능성(SAT)이 NP-완전임을 보였고(Cook 1971), Karp 는 1972년 20개 문제를 더 NP-완전으로 보이며 P · NP 표기를 굳혔다(Karp 1972).
P = NP 인지는 지금도 Clay 수학연구소의 밀레니엄 상금 문제로 열려 있다(Clay P vs NP). 인터넷 금융 거래의 보안도 인수분해가 어렵다는 복잡도 가정에 기대므로(Cook P vs NP 설명서 3절), 알고리즘 분석의 결론은 성능뿐 아니라 보안 판단의 근거가 된다.
3쉽게 이해하기 — 스위치 자물쇠를 맡은 열쇠공
열쇠공 박 씨는 주인이 번호를 잊은 창고 자물쇠를 맡았다. 자물쇠에는 켜고 끄는 스위치가 6개라 조합이 64가지이고, 스위치가 하나 늘 때마다 조합은 두 배가 된다. 주인이 적어 둔 쪽지를 찾아오면 한 번 맞춰 보면 끝나지만, 쪽지가 없으면 평균 절반쯤을 돌려 봐야 한다. 박 씨는 하루 작업 시간에 스위치 몇 개짜리까지 열 수 있는지 어림해서 일을 받을지 정한다.
그림 1 · 열쇠공은 조합 수를 세고(시간 복잡도), 쪽지로 맞춰 보기가 쉬운지 보고(NP), 평균과 하루 한도를 어림해(확률 · 수치 해석) 일을 받을지 정한다.
그림 2 · 쪽지가 없으면 조합을 차례로 돌려야 하지만 쪽지가 있으면 한 번에 끝난다 — 실제로도 찾기(탐색)와 맞춰 보기(검증)의 비용이 갈리고, 그 차이가 P 와 NP 의 경계다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 열쇠공 박 씨 | 알고리즘 분석 | 절차의 비용을 세고 문제를 부류로 나눠 풀 방법을 고른다 |
| 스위치 자물쇠 | 결정 문제 · 입력 크기 n | «예 · 아니요»로 답하는 문제와 그 입력 길이다 |
| 조합 세기 | 시간 복잡도(Big-O) | 연산 수가 n 에 따라 늘어나는 차수를 적는다 |
| 쪽지 | 인증서 · NP | 답 후보가 주어지면 다항 시간에 맞는지 확인한다 |
| 평균 어림 | 확률 · 베이즈 정리 | 입력이 무작위일 때 기대 비용과 틀릴 확률을 셈한다 |
| 하루 한도 셈 | 수치 해석(보간 · 비선형 방정식) | 식으로 풀리지 않는 값을 반복 계산으로 어림한다 |
| 일 받기 | P · NP 문제 | 다항이면 정확히 풀고, NP-난해면 근사 · 휴리스틱으로 넘긴다 |
⚠ 비유가 맞지 않는 곳: 자물쇠는 단서가 없는 비밀이라 차례로 돌리는 것이 최선임이 분명하지만, 부분집합 합 같은 NP-완전 문제는 빠른 방법이 «없다고 증명된» 것이 아니라 «아직 찾지 못한» 것이다(Cook P vs NP 설명서 3절).
4구조 — 시간 복잡도 · P · NP 문제 · 확률과 수치 해석
시간 복잡도가 절차의 비용을 n 의 차수로 세면, P · NP 문제는 그 차수가 다항인지 지수인지로 문제 자체를 나눈다. 확률과 수치 해석은 평균 비용 · 한계 크기처럼 셈이 막히는 곳을 푸는 도구라 알고리즘 분석에 함께 있다.
그림 3 · 자료구조 · 설계 기법 · 그래프 알고리즘의 절차를 시간 복잡도가 세고, P · NP 문제가 그 차수로 가르며, 확률 · 수치 해석이 평균과 한계 n 을 보태 판단이 나온다.
| 아래 토픽 | 묻는 질문 | 다루는 값 | 대표 결과 |
|---|---|---|---|
| 시간 복잡도(Big-O) | n 이 커지면 연산 · 메모리가 얼마나 느나 | 연산 수 · 메모리 사용량 | O(n log n) · O(n·2ⁿ)(NIST DADS big-O) |
| P · NP 문제 | 다항 시간에 풀리나, 검증만 다항인가 | 결정 문제 · 인증서 · 환원 | P ⊆ NP · NP-완전 · NP-난해(Cook P vs NP 설명서 1절) |
| 확률 · 베이즈 정리 | 입력이 무작위일 때 평균은 얼마이고 틀릴 확률은 | 기대값 · 조건부 확률 | 평균 비용 · 무작위 알고리즘 오류율(NIST DADS randomized) |
| 수치 해석(보간 · 비선형 방정식) | 식으로 못 푸는 값을 몇 번 반복해 얼마나 정확히 | 오차 · 수렴 차수 | 뉴턴 2차 · 할선 약 1.618(DLMF 3.8) · Lagrange 보간 오차항(DLMF 3.3) |
🔑 시간 복잡도는 «이 절차가 얼마나 드나»를, P · NP 는 «이 문제를 다항으로 푸는 절차가 있기나 한가»를 묻는다 — 앞은 절차를 바꾸면 달라지고 뒤는 문제가 정한다.
5동작 — 부분집합 합 한 건의 분석
수 6개 묶음에서 합이 26 인 부분이 있는지 묻는 결정 문제를 네 토픽이 차례로 다룬다. 수 묶음과 초당 10⁹ 번 연산은 설명용 가정 값이다.
- 문제 — {7, 11, 5, 13, 2, 9} 에서 합이 26 인 부분집합이 있는가(n = 6).
- 세기(시간 복잡도) — 부분집합 2⁶ = 64개 × 덧셈 최대 6번 = 최악 384번 → O(n·2ⁿ) · 메모리는 지금 고른 묶음 하나라 O(n).
- 검증(P · NP) — 후보 {11, 13, 2} 를 받으면 덧셈 2번 · 비교 1번으로 «예»를 확인한다 → 검증이 다항이라 NP 이고, 부분집합 합은 NP-완전이다(Cook P vs NP 설명서 3절).
- 평균(확률) — 답이 하나뿐이고 64개 중 어디든 같은 확률이면, 찾자마자 멈추는 탐색의 기대 조사 수는 (64 + 1) ÷ 2 = 32.5개 → 평균도 2ⁿ 차수다.
- 한계 식(수치 해석) — 1초 예산 n·2ⁿ = 10⁹ 는 식으로 풀리지 않아 f(n) = n ln 2 + ln n − ln 10⁹ 에 뉴턴법을 쓴다 — 30 → 25.22 → 25.24, 두 번에 소수 둘째 자리까지 맞는다(DLMF 3.8(ii)). 이분법은 [1, 64] 를 폭 0.01 까지 줄이는 데 13번이 든다.
- 판정 — n = 25 는 8.4억 번이라 1초 안이고 n = 26 은 17.4억 번이라 넘는다 · 기계를 10배로 해도 n·2ⁿ = 10¹⁰ 의 해는 28.39 → n = 28.
- 넘기기 — 더 큰 n 은 정확 탐색을 버리고 동적 계획법 표(6 × 27 = 162칸 · 목표 합에 비례)나 근사로 → 알고리즘 설계 기법.
그림 4 · 같은 문제를 시간 복잡도가 세고(②) P · NP 가 분류하며(③) 확률 · 수치 해석이 평균과 한계 n 을 보태(④ ⑤), 1초 안 정확 탐색은 n = 25 까지라는 판정(⑥)이 나온다.
그림 5 · 같은 1초에서 기계를 10배로 늘리면 다항 시간 절차는 풀 수 있는 n 이 곱으로 늘지만, 지수 시간 절차는 n 에 3 ~ 4가 더해질 뿐이다.
🔑 다항 시간 문제는 기계를 바꾸면 감당하는 크기가 곱으로 늘지만, 지수 시간 문제는 기계 대신 문제를 바꿔야(근사 · 제약 추가) 크기가 는다.
6비교 — 관련 기술과의 경계
| 토픽 | 맡는 일 | 경계 | 넘기는 곳 |
|---|---|---|---|
| 알고리즘 분석 | 비용을 세고 문제의 부류를 가름 | 절차를 짜지 않고 잰다 | — |
| 자료구조 | 데이터 배치와 연산 하나의 비용 | 연산 비용 «값»은 그쪽, 세는 방법은 이쪽 | 스택 · 큐 · 해시 테이블 |
| 알고리즘 설계 기법 | 쪼개기 · 저장 · 즉시 선택 · 무작위로 절차를 짬 | NP-난해 판정 뒤의 근사 · 휴리스틱 설계는 그쪽 | 동적 계획법 · 휴리스틱 탐색(A*) · 몬테카를로 방법 |
| 그래프 알고리즘 | 탐색 · 최단 경로 · MST 절차 | 알고리즘별 비용 계산은 그쪽 | 최단 경로(다익스트라 · 벨만-포드) |
| 시스템 성능 · 용량 관리 | 실측 응답 시간 · 서버 대수 | 차수는 이쪽, 실측 상수는 그쪽 | BMT · 용량 산정 |
분석«입력이 커지면 어떻게 되나 · 이 문제가 원래 얼마나 어려운가»는 알고리즘 분석, «어떻게 짜나»는 설계 기법 · 그래프 알고리즘, «지금 몇 ms 인가»는 시스템 성능 · 용량 관리에서 본다. 근거는 표의 「경계」 열 — 분석 결과는 상수를 버린 차수와 다항 · 지수 부류(Cook P vs NP 설명서 1절의 다항 시간 정의)라 실측값을 대신하지 못한다.
7실무 진단 — 느림 · 멈춤을 아래 토픽으로 가르기
분석먼저 n 을 1 · 2 늘려 시간 비가 일정한지(지수) 줄어드는지(다항) 보고, 그다음 같은 n 에서 실행마다 갈리는지(분포)를 본다. 지수로 판정되면 구현 손질보다 문제의 결정판이 NP-완전인지 확인하는 것이 먼저다(NIST DADS NP-hard).
| # | 증상 | 의심 원인 | 아래 토픽 | 확인 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 항목 하나 늘 때마다 시간이 거의 2배 | 조합 전수 탐색 | P · NP 문제 | n · n+1 · n+2 의 실행 시간 비 | 비가 일정(≈ 2)하면 지수 → 결정판이 NP-완전 목록에 있는지 대조(NIST DADS NP-complete) |
| 2 | 평균은 빠른데 가끔 수십 배 느림 | 최악 입력이 몰림 | 확률 · 베이즈 정리 | 실행 시간 분포(중앙값 · 상위 1%) | 평균의 정의와 입력 가정부터 확인(NIST DADS average case) · 고정된 최악은 무작위 선택으로 피함(NIST DADS randomized) |
| 3 | 근사 해 반복이 끝나지 않음 | 중근 · 나쁜 시작점 | 수치 해석(보간 · 비선형 방정식) | 반복마다 오차 |f(x)| 기록 | 오차가 매번 제곱으로 줄지 않으면 중근 의심 · 부호가 바뀌는 구간이 있으면 이분법으로(DLMF 3.8(ii) · 3.8(iii)) |
| 4 | 속도는 되는데 메모리 부족으로 멈춤 | 표 크기가 입력 값에 비례 | 시간 복잡도(Big-O) | 표 칸 수 × 칸 크기 | 칸 수가 n · 목표 값에 비례하면 공간 복잡도 문제 → 한 줄씩 다시 쓰는 표로 |
8시험 대비
시험에서는 P · NP · NP-완전 · NP-난해의 정의와 포함 관계를 묻는 정의 · 특징형, 다항 시간과 지수 시간 알고리즘의 차이를 견주는 비교형으로 나올 수 있다. 정의 · 특징형이면 «세기 → 분류 → 사례» 순서로 쓰고, 비교형이면 그림 5 처럼 같은 예산에서 풀 수 있는 n 을 숫자로 보이는 것이 좋다.
- 개요 — 계산 복잡도 정의 · 시간 · 공간 복잡도 · 다항 시간 = «좋은 알고리즘»(Edmonds · Cook P vs NP 설명서)
- 구조 — 그림 3(세기 · 가르기 · 확률 · 수치 해석의 관계)
- 복잡도 부류 — 표(P ⊆ NP · NP-완전 · NP-난해 · 인증서 검증 · 환원 · Cook 1971 · Karp 1972)
- 사례 — 그림 4 부분집합 합(최악 384번 · 검증 3번 · 기대 32.5개 · 한계 n = 25)
- 비교 — 그림 5 다항 ↔ 지수(기계 10배 → n ×10 · ×3.16 · +3)
- 시사점 — 근사 · 휴리스틱으로 넘김 · 복잡도 가정에 기대는 암호(인수분해)
꼭 쓸 키워드
시간 복잡도공간 복잡도다항 시간지수 시간NP-완전NP-난해환원인증서기대값수렴 차수
다른 답안과 차이를 내는 한 가지는 «기계를 10배 빠르게 해도 지수 시간 절차는 n 에 3 ~ 4만 더한다»를 그림 5 의 숫자로 보이는 것이다.
9오해와 사실
- 오해NP 는 «다항 시간에 풀 수 없는 문제»라는 뜻이다.사실NP 는 답을 다항 시간에 검증할 수 있는 결정 문제의 부류이고(NIST DADS NP), P 의 문제도 모두 NP 에 든다(Cook P vs NP 설명서 1절).
- 오해부분집합 합은 동적 계획법으로 O(n · T) 에 풀리니 P 에 든다.사실T 는 목표 합의 «값»이라 자릿수 d 에 대해 10ᵈ 까지 커지므로 입력 길이에는 지수이고, 십진 표기 부분집합 합은 NP-완전으로 꼽힌다(Cook P vs NP 설명서 3절).
- 오해평균 비용이 낮으면 최악은 신경 쓰지 않아도 된다.사실평균은 어떤 입력이 얼마나 나온다는 가정에 달려 있어(NIST DADS average case) 가정이 틀리면 무너지고, 사례의 기대 32.5개도 여전히 2ⁿ 차수다.
10핵심 정리
| 아래 토픽 · 개념 | 재는 것 | 사례 값 | 실무 신호 | 넘기는 곳 |
|---|---|---|---|---|
| 시간 복잡도 | 연산 수의 차수 | 최악 384번 = 6 · 2⁶ | n 을 늘린 시간 비 | 자료구조 · 그래프 알고리즘의 개별 비용 |
| 공간 복잡도 | 메모리 사용량의 차수 | 표 162칸 | 메모리 부족 멈춤 | 동적 계획법 표 줄이기 |
| P | 다항 시간에 풀림 | 최단 경로 · MST | 기계 증설이 곱으로 효과 | 그래프 알고리즘 |
| NP-완전 | 검증은 다항 · 가장 어려운 NP | 부분집합 합 · SAT | 항목 하나에 시간 2배 | 근사 · 휴리스틱(설계 기법) |
| NP-난해 | 결정판이 NP-완전인 최적화 | 최단 순회 찾기 | 최적해 계산이 업무 시간 초과 | 휴리스틱 탐색(A*) |
| 확률 · 베이즈 정리 | 기대 비용 · 틀릴 확률 | 기대 32.5개 | 실행마다 시간이 갈림 | 무작위 알고리즘(몬테카를로 방법) |
| 수치 해석 | 반복 횟수 · 수렴 차수 | 뉴턴 2번 · 이분법 13번 | 반복이 끝나지 않음 | 머신러닝(수치 최적화) |
11참고 문헌
- 먼저 볼 문헌
- ★ The P versus NP Problem (Stephen Cook · Clay Mathematics Institute official problem description) — P · NP 의 정식 정의(검사 관계)와 NP-완전의 역사 · 암호와의 관계를 볼 때
- ★ Dictionary of Algorithms and Data Structures - NP — NP 가 «빨리 찾는다»가 아니라 «빨리 검증한다»는 뜻임을 확인할 때
- ★ NIST Digital Library of Mathematical Functions §3.8 Nonlinear Equations — 이분법 · 뉴턴법 · 할선법의 수렴 차수를 볼 때
- ★ Millennium Prize Problems - P vs NP — P · NP 문제가 미해결 상금 문제로 남아 있는 현황을 볼 때
- 본문 근거
- Dictionary of Algorithms and Data Structures - NP-complete — NIST · 2021-04 ·
xlinux.nist.gov/dads/HTML/npcomplete.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - NP-hard — NIST · 2021-01 ·
xlinux.nist.gov/dads/HTML/nphard.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - average case — NIST · 2019-08 ·
xlinux.nist.gov/dads/HTML/averagecase.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - randomized algorithm — NIST · 2019-02 ·
xlinux.nist.gov/dads/HTML/randomizedAlgo.html· 확인 2026-11-14 - NIST Digital Library of Mathematical Functions §3.3 Interpolation — NIST · 2026-11 ·
dlmf.nist.gov/3.3· 확인 2026-11-14 - Cook 1971 The complexity of theorem-proving procedures (STOC 1971 · 151-158) — ACM · 1971-05 ·
doi.org/10.1145/800157.805047· 확인 2026-11-14 - Karp 1972 Reducibility among combinatorial problems (Complexity of Computer Computations · 85-103) — Plenum Press · Springer · 1972-03 ·
doi.org/10.1007/978-1-4684-2001-2_9· 확인 2026-11-14