소프트웨어 복잡도(Software Complexity)는 코드의 유지보수성, 오류 가능성, 테스트 용이성을 판단하는 핵심 지표로 자주 출제되는 영역입니다. 암기할 것 위주로 정리합니다.
1. McCabe의 순환 복잡도 (Cyclomatic Complexity)
가장 출제 빈도가 높습니다. 제어 흐름 그래프(Control Flow Graph)를 기반으로 프로그램 내의 독립적인 경로의 수를 측정합니다. (기본 경로 Basic Path)
[공식 1] (그래프 이용):
$V(G) = E - N + 2P$
$E$: 간선(Edges) 수
$N$: 노드(Nodes) 수
$P$: 연결된 성분의 수 (보통 단일 프로그램이면 1)
[공식 2] (분기점 이용):
$V(G) = \text{화살표로 둘러싸인 영역(Region)의 수}$
[공식 3] (조건문 이용):
$V(G) = \text{조건문(Predicate)의 개수} + 1$
2. Halstead의 소프트웨어 사이언스 (Software Science)
코드의 라인 수 대신 연산자(Operator)와 피연산자(Operand)의 개수를 분석하여 복잡도를 측정합니다.
[기본 지표]
$n_1$: 서로 다른 연산자의 수 / $n_2$: 서로 다른 피연산자의 수
$N_1$: 전체 연산자의 총 개수 / $N_2$: 전체 피연산자의 총 개수
[암기 공식]
- 어휘량 (Vocabulary): $n = n_1 + n_2$
- 전체 길이 (Length): $N = N_1 + N_2$
- 예측 길이 ($\hat{N}$): $\hat{N} = n_1 \log_2 n_1 + n_2 \log_2 n_2$
- 부피 (Volume): $V = N \times \log_2 n$
- 노력 (Effort): $E = V \times D$ (여기서 $D$는 난이도)
3. Knot 카운트 (Knot Count)
주로 FORTRAN이나 조기 언어에서 사용되던 개념으로, 제어 흐름의 교차(Crossing)를 측정합니다.
[개념] : 프로그램 실행 경로가 서로 엉켜있는 지점(Knot)의 개수를 셉니다.
[특징] : GOTO 문을 남발할수록 Knot Count가 증가합니다. 구조적 프로그래밍(Structured Programming)에서는 이 값이 0에 가깝습니다. 현대 시험에서는 "비구조적 프로그래밍의 복잡도 측정"이라는 키워드로 등장합니다.
4. Chen의 복잡도 (Chen's Complexity)
McCabe의 순환 복잡도를 보완한 개념으로, 선택문의 중첩(Nesting)에 가중치를 둡니다.
[핵심] : 단순히 조건문의 개수만 세는 것이 아니라, if 문 안에 if 문이 들어가는 중첩 깊이가 깊어질수록 복잡도가 기하급수적으로 높다고 판단합니다.
[공식] : $Z(G) = \sum_{i=1}^{n} (i \times \text{해당 깊이의 조건문 수})$
(구체적인 수식보다는 '중첩도 반영'이라는 특징이 중요합니다.)
5. 추가적인 복잡도 측정 방법
시험 대비를 위해 아래 두 가지도 함께 알아두시면 좋습니다.
| 방법론 | 특징 |
| Lines of Code (LOC) | 단순 코드 라인 수. 가장 원시적이지만 직관적임. |
| Function Point (FP) | 사용자 관점에서 소프트웨어 기능을 정량화 (입력, 출력, 질의, 파일 등). |
| Henry & Kafura | 정보 흐름(Information Flow) 복잡도. 공식을 암기하세요. |
[Henry & Kafura 공식] (매우 중요)
$\text{Complexity} = \text{Length} \times (\text{Fan-in} \times \text{Fan-out})^2$
- Fan-in : 해당 모듈을 호출하는 모듈 수
- Fan-out : 해당 모듈이 호출하는 모듈 수
[문제] 모듈 A의 크기가 10라인이고, 모듈 A를 호출하는 모듈이 3개, 모듈 A가 호출하는 모듈이 2개일 때 Henry & Kafura 복잡도는?
[풀이]
Length (길이): 10
Fan-in (유입): 3
Fan-out (유출): 2
계산: $10 \times (3 \times 2)^2 = 10 \times 6^2 = 10 \times 36 = 360$
💡 수험생을 위한 한 줄 요약
- McCabe : 화살표, 노드, 조건문+1 (가장 출제율 높음)
- Halstead : 연산자($n_1, N_1$)와 피연산자($n_2, N_2$)의 조합
- Knot : 제어선의 교차 횟수 (GOTO 관련)
- Chen : 제어 구조의 중첩(Nesting) 강조
- Henry & Kafura : $L \times (\text{In} \times \text{Out})^2$ (Fan-in/out 문제로 자주 출제)