CNN과 Attention 복잡도 (Complexity) 비교

1. 2D CNN 연산 복잡도

2D CNN의 총 연산량은 다음과 같은 공식으로 계산됩니다:

기호	의미
$H_{out}, W_{out}$	출력 feature map의 세로/가로 크기
$C_{in}$	입력 채널 수 (예: RGB = 3)
$K_H, K_W$	커널 높이, 너비 (예: 3×3)
$C_{out}$	출력 채널 수 (필터 개수)

간단화 형태

입력과 출력 크기가 동일하다고 가정하면:

---

2. 예시 계산

• 입력: 128×128 이미지, 채널 수 = 3 (RGB)
• 커널: 3×3
• 출력 채널 수: 64
• stride = 1, padding = 1 (출력 크기 유지)

---

3. CNN vs Self-Attention 복잡도 비교

항목	Self-Attention	CNN
연산 복잡도	$O(n^2 \cdot d)$	$O(k \cdot n \cdot d^2)$
연산 기준	모든 토큰쌍 간 유사도	각 위치에서 이웃 위치의 특징 추출
차원 곱	$d$ (vector 간 내적)	$d^2$ (입력/출력 채널 간 FC 변환)
병렬화 가능성	높음 (전체 토큰 동시 처리)	높음 (모든 위치, 커널 병렬 처리)

핵심 차이:

• Attention은 “쌍 간 관계” 중심 → $n^2$
• CNN은 “채널 간 변환” 중심 → $d^2$