#divide-and-conquer

3개 글

Karatsuba Multiplication두 개의 $n$자리 정수 $x$와 $y$를 곱한다고 하자.2026년 7월 28일4분 읽기
Master Theorem병합 정렬의 시간 복잡도를 구한다고 하자.2026년 7월 28일8분 읽기
Strassen Algorithm$n \times n$ 행렬 $A$와 $B$의 곱 $C = AB$를 정의대로 계산하면 각 $C{ij} = \sum{k=1}^{n} A{ik} B{kj}$에 $n$번의 곱셈이 들고, 원소가 $n^2$개이므로 총 $\Theta(n^3)$번의 스칼라 곱셈이 필요하다.2026년 7월 28일3분 읽기