IT › 컴퓨터 시스템 › 알고리즘

알고리즘 분석(계산 복잡도)Algorithm Analysis and Computational Complexity

알고리즘에서 절차의 시간 · 공간 비용을 입력 크기로 세고, 그 비용이 다항인지 지수인지로 문제의 어려움을 가르는 일이다. 평균 비용을 셈하는 확률과 근사 해의 반복 횟수를 다루는 수치 해석을 도구로 함께 둔다.

1요약

  1. 알고리즘 분석은 알고리즘 가운데 비용을 세고 문제의 어려움을 가르는 갈래로, 시간 복잡도(Big-O) · P · NP 문제 · 확률 · 베이즈 정리 · 수치 해석 네 토픽이 자료구조 · 설계 기법 · 그래프 알고리즘의 절차를 같은 잣대로 잰다.
  2. 비용을 세지 않으면 «더 빠른 기계»가 답처럼 보인다 — 부분집합 합 전수 탐색은 초당 10⁹ 번 연산(가정 값)에서 1초 안 n = 25 이고, 기계를 10배로 늘려도 n = 28 에 그친다(원문 식 직접 계산 · 그림 5).
  3. 「입력이 조금 늘었는데 너무 느려졌다」는 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가지이고, 스위치가 하나 늘 때마다 조합은 두 배가 된다. 주인이 적어 둔 쪽지를 찾아오면 한 번 맞춰 보면 끝나지만, 쪽지가 없으면 평균 절반쯤을 돌려 봐야 한다. 박 씨는 하루 작업 시간에 스위치 몇 개짜리까지 열 수 있는지 어림해서 일을 받을지 정한다.

박 씨와 자물쇠 문제 입력 · n = 6 켜고 끄는 스위치 6개 조합 64가지 조합 세기 1 시간 복잡도(Big-O) 스위치 하나 늘면 2배 7개면 128가지 쪽지 맞춰 보기 2 NP · 다항 시간 검증 쪽지 조합을 한 번 돌림 맞으면 바로 열림 평균 어림 3 확률 · 기대값 쪽지가 없으면 평균 32번쯤 돌림 하루 한도 셈 4 수치 해석 · 근사 해 하루에 스위치 몇 개까지 계산자로 어림 일 받기 5 P · NP 판단 한도 안이면 직접 열고 넘으면 다른 방법 문제 입력 세기 검증 · 판정 수학 도구 사람의 판단 이야기 순서

그림 1 · 열쇠공은 조합 수를 세고(시간 복잡도), 쪽지로 맞춰 보기가 쉬운지 보고(NP), 평균과 하루 한도를 어림해(확률 · 수치 해석) 일을 받을지 정한다.

자물쇠 받기스위치 6개
조합 세기하나 늘면 2배
쪽지 맞춰 보기한 번에 확인
평균 어림절반쯤 돌림
하루 한도 셈스위치 몇 개까지
일 받기열지 말지 정함
비유 — 돌려 보기와 맞춰 보기 실제 — 탐색과 검증 쪽지 없음 · 스위치 3개 000 001 010 011 100 101 110 111 차례로 돌려 여섯째에 열림 → 최악 8번 탐색 후보 2ⁿ 개를 차례로 시험 n = 3 → 8번 · n = 30 → 약 10.7억 번 NP-완전 문제는 다항 방법이 알려지지 않음 쪽지 있음 · 「101」 101 적힌 대로 한 번 맞춰 봄 → 1번 검증 인증서 하나를 다항 시간에 확인 부분집합 합 = 덧셈 n − 1번 · 비교 1번 검증이 다항이면 그 문제는 NP P = 찾기도 다항 · NP = 맞춰 보기가 다항 · 둘이 같은가(P = NP)는 아직 모른다 탐색(세기) 검증 굵은 테두리 = 맞는 조합

그림 2 · 쪽지가 없으면 조합을 차례로 돌려야 하지만 쪽지가 있으면 한 번에 끝난다 — 실제로도 찾기(탐색)와 맞춰 보기(검증)의 비용이 갈리고, 그 차이가 P 와 NP 의 경계다.

비유 속 역할실제 이름실제로 하는 일
열쇠공 박 씨알고리즘 분석절차의 비용을 세고 문제를 부류로 나눠 풀 방법을 고른다
스위치 자물쇠결정 문제 · 입력 크기 n«예 · 아니요»로 답하는 문제와 그 입력 길이다
조합 세기시간 복잡도(Big-O)연산 수가 n 에 따라 늘어나는 차수를 적는다
쪽지인증서 · NP답 후보가 주어지면 다항 시간에 맞는지 확인한다
평균 어림확률 · 베이즈 정리입력이 무작위일 때 기대 비용과 틀릴 확률을 셈한다
하루 한도 셈수치 해석(보간 · 비선형 방정식)식으로 풀리지 않는 값을 반복 계산으로 어림한다
일 받기P · NP 문제다항이면 정확히 풀고, NP-난해면 근사 · 휴리스틱으로 넘긴다

⚠ 비유가 맞지 않는 곳: 자물쇠는 단서가 없는 비밀이라 차례로 돌리는 것이 최선임이 분명하지만, 부분집합 합 같은 NP-완전 문제는 빠른 방법이 «없다고 증명된» 것이 아니라 «아직 찾지 못한» 것이다(Cook P vs NP 설명서 3절).

4구조 — 시간 복잡도 · P · NP 문제 · 확률과 수치 해석

시간 복잡도가 절차의 비용을 n 의 차수로 세면, P · NP 문제는 그 차수가 다항인지 지수인지로 문제 자체를 나눈다. 확률과 수치 해석은 평균 비용 · 한계 크기처럼 셈이 막히는 곳을 푸는 도구라 알고리즘 분석에 함께 있다.

세고 → 가르고 → 판단한다 분석 대상 절차 자료구조 설계 기법 그래프 알고리즘 시간 복잡도(Big-O) 연산 · 메모리를 n 의 차수로 셈 O(n log n) · O(n·2ⁿ) P · NP 문제 다항 시간에 풀리나 검증만 다항인가 NP-완전 · NP-난해 판단 정확 탐색 가능 n 근사로 넘길지 기계 증설 효과 확률 · 베이즈 정리 평균 · 기대 비용 틀릴 확률 평균 비용 수치 해석(보간 · 비선형 방정식) 근사 해 · 반복 횟수 · 수렴 차수 한계 n 을 방정식으로 풂 한계 n 분석 대상 세기 가르기 수학 도구 판단(결과)

그림 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⁹ 번 연산은 설명용 가정 값이다.

  1. 문제 — {7, 11, 5, 13, 2, 9} 에서 합이 26 인 부분집합이 있는가(n = 6).
  2. 세기(시간 복잡도) — 부분집합 2⁶ = 64개 × 덧셈 최대 6번 = 최악 384번 → O(n·2ⁿ) · 메모리는 지금 고른 묶음 하나라 O(n).
  3. 검증(P · NP) — 후보 {11, 13, 2} 를 받으면 덧셈 2번 · 비교 1번으로 «예»를 확인한다 → 검증이 다항이라 NP 이고, 부분집합 합은 NP-완전이다(Cook P vs NP 설명서 3절).
  4. 평균(확률) — 답이 하나뿐이고 64개 중 어디든 같은 확률이면, 찾자마자 멈추는 탐색의 기대 조사 수는 (64 + 1) ÷ 2 = 32.5개 → 평균도 2ⁿ 차수다.
  5. 한계 식(수치 해석) — 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번이 든다.
  6. 판정 — n = 25 는 8.4억 번이라 1초 안이고 n = 26 은 17.4억 번이라 넘는다 · 기계를 10배로 해도 n·2ⁿ = 10¹⁰ 의 해는 28.39 → n = 28.
  7. 넘기기 — 더 큰 n 은 정확 탐색을 버리고 동적 계획법 표(6 × 27 = 162칸 · 목표 합에 비례)나 근사로 → 알고리즘 설계 기법.
1 문제 {7, 11, 5, 13, 2, 9} 합 26 인 부분? n = 6 · 결정 문제 2 세기 64개 × 덧셈 6번 최악 384번 O(n·2ⁿ) 3 검증 후보 {11, 13, 2} 덧셈 2 · 비교 1 다항 검증 → NP 4 평균 답 1개 · 위치 무작위 (64 + 1) ÷ 2 기대 32.5개 조사 5 한계 식 n·2ⁿ = 10⁹ 뉴턴 30 → 25.22 → 25.24 (2번) 6 판정 n = 25 : 8.4억 번 n = 26 : 17.4억 번 1초 안 = 25 까지 7 넘기기 동적 계획법 표 6 × 27 = 162칸 설계 기법 문제 입력 세기(시간 복잡도) 검증 · 판정(P · NP) 수학 도구 넘기는 곳 수 묶음 · 초당 10⁹ 번 연산 = 설명용 가정 값 · 연산 수 = 원문 식 직접 계산

그림 4 · 같은 문제를 시간 복잡도가 세고(②) P · NP 가 분류하며(③) 확률 · 수치 해석이 평균과 한계 n 을 보태(④ ⑤), 1초 안 정확 탐색은 n = 25 까지라는 판정(⑥)이 나온다.

기계를 10배로 늘리면 풀 수 있는 최대 n 은? 차수 1초(10⁹ 번) 10배(10¹⁰ 번) 늘어난 정도 O(n) 10억 100억 ×10 O(n²) 31,623 100,000 ×3.16 O(n³) 1,000 2,154 ×2.15 O(2ⁿ) 29 33 +4 (×1.14) O(n·2ⁿ) 25 28 +3 (×1.12) 다항 시간 — 곱으로 는다 지수 시간 — 덧셈으로 는다 막대 = 최대 n 의 배수 − 1 · 원문 식 직접 계산

그림 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 을 숫자로 보이는 것이 좋다.

답안 목차
  1. 개요 — 계산 복잡도 정의 · 시간 · 공간 복잡도 · 다항 시간 = «좋은 알고리즘»(Edmonds · Cook P vs NP 설명서)
  2. 구조 — 그림 3(세기 · 가르기 · 확률 · 수치 해석의 관계)
  3. 복잡도 부류 — 표(P ⊆ NP · NP-완전 · NP-난해 · 인증서 검증 · 환원 · Cook 1971 · Karp 1972)
  4. 사례 — 그림 4 부분집합 합(최악 384번 · 검증 3번 · 기대 32.5개 · 한계 n = 25)
  5. 비교 — 그림 5 다항 ↔ 지수(기계 10배 → n ×10 · ×3.16 · +3)
  6. 시사점 — 근사 · 휴리스틱으로 넘김 · 복잡도 가정에 기대는 암호(인수분해)

꼭 쓸 키워드
시간 복잡도공간 복잡도다항 시간지수 시간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참고 문헌

  1. 먼저 볼 문헌
  2. ★ The P versus NP Problem (Stephen Cook · Clay Mathematics Institute official problem description) — P · NP 의 정식 정의(검사 관계)와 NP-완전의 역사 · 암호와의 관계를 볼 때
    Clay Mathematics Institute · 2022-06 · www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf · 확인 2026-11-14
  3. ★ Dictionary of Algorithms and Data Structures - NP — NP 가 «빨리 찾는다»가 아니라 «빨리 검증한다»는 뜻임을 확인할 때
    NIST · 2021-01 · xlinux.nist.gov/dads/HTML/np.html · 확인 2026-11-14
  4. ★ NIST Digital Library of Mathematical Functions §3.8 Nonlinear Equations — 이분법 · 뉴턴법 · 할선법의 수렴 차수를 볼 때
    NIST · 2026-11 · dlmf.nist.gov/3.8 · 확인 2026-11-14
  5. ★ Millennium Prize Problems - P vs NP — P · NP 문제가 미해결 상금 문제로 남아 있는 현황을 볼 때
    Clay Mathematics Institute · 2026-11 · www.claymath.org/millennium/p-vs-np/ · 확인 2026-11-14
  6. 본문 근거
  7. Dictionary of Algorithms and Data Structures - NP-complete — NIST · 2021-04 · xlinux.nist.gov/dads/HTML/npcomplete.html · 확인 2026-11-14
  8. Dictionary of Algorithms and Data Structures - NP-hard — NIST · 2021-01 · xlinux.nist.gov/dads/HTML/nphard.html · 확인 2026-11-14
  9. Dictionary of Algorithms and Data Structures - average case — NIST · 2019-08 · xlinux.nist.gov/dads/HTML/averagecase.html · 확인 2026-11-14
  10. Dictionary of Algorithms and Data Structures - randomized algorithm — NIST · 2019-02 · xlinux.nist.gov/dads/HTML/randomizedAlgo.html · 확인 2026-11-14
  11. NIST Digital Library of Mathematical Functions §3.3 Interpolation — NIST · 2026-11 · dlmf.nist.gov/3.3 · 확인 2026-11-14
  12. Cook 1971 The complexity of theorem-proving procedures (STOC 1971 · 151-158) — ACM · 1971-05 · doi.org/10.1145/800157.805047 · 확인 2026-11-14
  13. 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