1. 딥러닝 네트워크의 대표 Layer

네 가지 레이어 유형에 대해 세 가지 항목을 비교합니다:

Layer Type	Complexity per Layer	Sequential Operations	Max Path Length
Self-Attention	$O(n^2·d)$	$O(1)$	$O(1)$
Recurrent (RNN)	$O(n·d^2)$	$O(n)$	$O(n)$
Convolutional	$O(k·n·d^2)$	$O(1)$	$O(log_k n)$
Self-Attention (restricted)	$O(r·n·d)$	$O(1)$	$O(n/r)$

여기서:

• $n$: 시퀀스 길이 (문장의 토큰 개수 등)
• $d$`: 각 토큰의 표현 차원 (보통 512 등)
• $k$: 커널 사이즈 (Convolutional layer에서)
• $r$: 제한된 self-attention의 neighborhood 크기

---

항목별 해설

1. Complexity per Layer (레이어별 연산량)

• Self-Attention:
  모든 토큰이 모든 토큰과 상호작용 → $O(n^2·d)$
  → 문장이 길어질수록 빠르게 느려짐

• Recurrent (RNN):
  각 토큰을 하나씩 처리 → $O(n·d^2)$

• Convolutional:
  토큰마다 주변 $k$개만 처리 → $O(k·n·d^2)$

• Restricted Self-Attention:
  r개의 이웃만 참조 → $O(r·n·d)$
  → Full attention보다 가볍지만 정보 범위 제한

---

2. Sequential Operations (병렬화 가능성)

• Self-Attention / Convolutional / Restricted Attention:
  모든 토큰을 한꺼번에 병렬 처리 가능 → $O(1)$

• Recurrent (RNN):
  앞 토큰의 결과가 있어야 다음 토큰을 처리 가능 → $O(n)$
  → 병렬화 어려움, 느림

---

3. Max Path Length (정보 전달 거리)

어떤 토큰이 다른 토큰의 정보를 전달받기까지 걸리는 최소 단계 수

• Self-Attention:
  모든 토큰이 한 번에 서로 연결됨 → $O(1)$

• RNN:
  앞에서 뒤로 차례대로 전달 → $O(n)$

• Convolutional:
  커널 크기 $k$인 conv를 $log$ 단계로 쌓음 → $O(log_k n)$

• Restricted Attention:
  $r$개씩만 보니까 전체에 도달하려면 $O(n/r)$ 단계

---

핵심 요약

항목	Self-Attention	RNN	CNN	Restricted Attention
연산량	많음 ($O(n^2·d)$)	중간	적당 ($O(k·n·d^2)$)	더 적음 ($O(r·n·d)$)
병렬화	아주 잘됨	잘 안됨	잘됨	잘됨
정보 전달 거리	가장 짧음 ($O(1)$)	가장 김 ($O(n)$)	중간 ($O(log_k n)$)	중간 ($O(n/r)$)

---

Transformer가 주목받는 이유 중 하나는:

병렬 처리에 강하면서도 전체 정보를 빠르게 전달할 수 있기 때문이에요.