資料結構›Ch1 演算法基礎
第 38 題/共 57 題
◀ DS 38/57
38. 分治法、遞迴式、Θ 分析、矩陣乘法
#DS-01-038中分治法遞迴式Θ 分析矩陣乘法

(10%) Consider three n×nn \times n matrices, denoted as AA, BB, and CC. Each of these matrices is partitioned into four n/2×n/2n/2 \times n/2 submatrices. Assuming that nn is an exact power of 2, we can guarantee that, for n≥2n \ge 2, the dimension n/2n/2 is an integer. The subdivisions for matrix AA yield A11A_{11}, A12A_{12}, A21A_{21}, and A22A_{22}. Similarly, matrix BB is decomposed into B11B_{11}, B12B_{12}, B21B_{21}, and B22B_{22}, while matrix CC undergoes division into C11C_{11}, C12C_{12}, C21C_{21}, and C22C_{22}. 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 C22C_{22} is invoked only once and '+' is matrix addition. Let T(n)T(n) represent the time required to process two n×nn \times n matrices using this particular procedure. Provide an asymptotic tight bound (Θ\Theta) for T(n)T(n), assuming that T(n)T(n) is a constant for sufficiently small nn.

📄 成大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎
本章題號 · 21–40 / 57