# Karatsuba

• 2026년 7월 27일 알고리즘
  카라츠바 알고리즘 — n자리 곱셈은 n²보다 빠를 수 있다

  n자리 두 수를 곱하는 데 정의대로면 Θ(n²)이 든다. 반으로 잘라 재귀해도 곱셈이 4번이라 여전히 n²이다. 카라츠바는 (x₁+x₂)(y₁+y₂) 하나로 곱을 3번으로 줄여 Θ(n^1.585)를 얻는다. Strassen의 8→7과 같은 구조를, 한 단계 더 단순한 무대에서 본다.