홍라이프 계산기그래프 알고리즘 실행 시간 추정기 쉽게 이해하기 — 개념과 원리
큰 그래프에서 탐색이나 최단 경로 알고리즘을 돌리기 전에, 몇 밀리초 만에 끝날지 몇 달이 걸릴지 미리 아는 것이 중요합니다. 이 추정기는 정점 수 V와 간선 수 E를 넣으면 대표적인 그래프 알고리즘 네 가지의 교과서 시간 복잡도로 연산 횟수를 구하고, 가정한 속도로 나누어 대략적인 실행 시간을 보여 줍니다.
계산 방법
- BFS/DFS: V + E회
- 이진 힙을 쓴 다익스트라: (V + E) · log₂ V회
- 벨만-포드: V · E회
- 플로이드-워셜: V³회
- 시간 = 연산 횟수 ÷ 초당 연산 수이며, ms, s, 일, 년으로 표시합니다.
원리
너비 우선 탐색과 깊이 우선 탐색은 정점을 한 번씩 방문하고 간선을 상수 번씩 확인하므로 작업량이 그래프 크기에 비례합니다. 다익스트라 알고리즘도 같은 방식으로 훑지만 아직 확정되지 않은 정점을 우선순위 큐에 두므로, 이진 힙에서는 갱신할 때마다 O(log V)가 듭니다. 벨만-포드는 음의 가중치를 다루기 위해 모든 간선을 최대 V − 1번 완화하므로 V · E입니다. 플로이드-워셜은 V에 대한 삼중 반복문으로 모든 정점 쌍의 최단 경로를 구하므로 E와 상관없이 V³입니다. 기본 속도 초당 10⁸회는 메모리 대기가 많은 실제 그래프 코드를 감안한 보수적인 값입니다.
예제 풀이
- 입력값: V = 100,000, E = 1,000,000, 초당 10⁸회입니다.
- BFS/DFS: 1,100,000 ÷ 10⁸ = 0.011초 = 11 ms입니다.
- 다익스트라: log₂ 100,000 ≈ 16.61이므로 약 18,270,000회, 183 ms입니다.
- 벨만-포드: 10⁵ × 10⁶ = 10¹¹회이므로 1,000 s입니다.
- 플로이드-워셜: 10¹⁵회, 즉 10⁷초를 86,400으로 나누면 약 116일입니다.
| 초당 연산 횟수 | BFS/DFS O(V + E) |
|---|---|
| 2.5e+07 | 44 ms |
| 5e+07 | 22 ms |
| 7.5e+07 | 14.7 ms |
| 1e+08 | 11 ms |
| 1.25e+08 | 8.8 ms |
| 1.5e+08 | 7.33 ms |
| 2e+08 | 5.5 ms |
결과 해석
질의 한 번이라면 1초 미만이면 충분하고, 질의가 수천 번이라면 그만큼 곱해서 판단합니다. 가중치가 음수가 아닌 단일 출발점 최단 경로라면 이 예에서는 다익스트라가 확실한 선택입니다. 벨만-포드는 음의 가중치가 있을 때만 비용을 치를 가치가 있으며, 변화가 없으면 일찍 멈추는 구현은 V − 1회보다 훨씬 빨리 끝나기도 합니다. 플로이드-워셜은 정점이 수천 개 이하일 때만 현실적입니다.
흔한 실수
- 음의 가중치가 있는 그래프에 다익스트라를 쓰면 틀린 답이 나올 수 있습니다.
- 메모리를 잊는 경우입니다. 플로이드-워셜은 V × V 거리표가 필요해 정점 100,000개, 4바이트면 40 GB입니다.
- 이 값을 정확한 시간으로 받아들이는 경우입니다.
자주 묻는 질문
피보나치 힙을 쓰면 다익스트라가 더 빠른가요?
이론상 O(E + V log V)이지만, 실제로는 상수가 작은 이진 힙이나 페어링 힙이 더 빠른 경우가 많습니다.
BFS와 DFS는 무엇이 다른가요?
BFS는 가중치 없는 그래프에서 간선 수 기준 최단 경로를 찾고, DFS는 사이클 검출과 위상 정렬에 알맞습니다.
플로이드-워셜은 왜 아직 배우나요?
코드가 짧고 음의 간선도 처리하며, 작고 조밀한 그래프에서는 효율적이기 때문입니다.
출처: E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 1959 · T. H. Cormen 외, Introduction to Algorithms, MIT Press