資料結構›Ch1 演算法基礎第 38 題/共 57 題
38. 分治法、遞迴式、Θ 分析、矩陣乘法
#DS-01-038中分治法遞迴式Θ 分析矩陣乘法
(10%) Consider three matrices, denoted as , , and . Each of these matrices is partitioned into four submatrices. Assuming that is an exact power of 2, we can guarantee that, for , the dimension is an integer. The subdivisions for matrix yield , , , and . Similarly, matrix is decomposed into , , , and , while matrix undergoes division into , , , and . We have the following procedure:
F(A, B)
n = A.rows
if n == 1
c11 = a11 · b11
else
C11 = F(A11, B11) + F(A12, B21)
C12 = F(A11, B12) + F(A12, B22)
C21 = F(A21, B11) + F(A22, B21)
C22 = F(A21, B12)
return C
It is important to note that the procedure for is invoked only once and '+' is matrix addition. Let represent the time required to process two matrices using this particular procedure. Provide an asymptotic tight bound () for , assuming that is a constant for sufficiently small .
📄 成大113
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎