大蓬数乘法 n2位n/2位 n/2位n/2位 X=A B XY=(A2 n/2+ B)(C2n/2+ D) 乘以2表示左移n位 AC2n+(AD+BC)2n/2+ BD T(n)=4T(x)+6(n) a=4b=2,f(n)=6(n),nl9g24=n f(n)=n9g24-,E=1, T(n)=6(ng24=6(n2 复杂性没有改善 11
大整数乘法 11 A B n/2位 X= n/2位 C D n/2位 Y= n/2位 XY = (A2n/2 + B)(C2n/2 + D) = AC2n + (AD+BC)2n/2 + BD 复杂性没有改善 ∵ 𝒂 = 𝟒, 𝒃 = 𝟐, 𝒇 𝒏 = 𝚯 𝒏 , 𝒏 log𝟐 𝟒 = 𝒏 𝟐 𝑻 𝒏 = 𝟒𝑻 𝒏 𝟐 + 𝚯 𝒏 𝒇 𝒏 = 𝒏 log𝟐 𝟒−𝜺 ,𝜺 = 𝟏, ∴ 𝑻 𝒏 = 𝚯(𝒏 log𝟐 𝟒 ) = 𝚯(𝒏 𝟐 ) 乘以2 n表示左移n位
大蓬数乘法 n2位n/2位 n/2位n/2位 X=A B XY=(A2n2+B)(C2m2+D)←乘以2表示左移位 AC2n+((A+B)(C+D)-AC-BD)2n/+ BD T(n)=3T()+6(n) a=3,b=2,f(m)=6(n),nlg3≈n159 f(n)=n9g23-,E≈0.59, T(n)=6(nlg23)=6(n159 复杂性降低了 12
大整数乘法 12 A B n/2位 X= n/2位 C D n/2位 Y= n/2位 XY = (A2n/2 + B)(C2n/2 + D) = AC2n + ((A+B)(C+D)-AC-BD)2n/2 + BD 复杂性降低了 ∵ 𝒂 = 𝟑, 𝒃 = 𝟐, 𝒇 𝒏 = 𝚯 𝒏 ,𝒏 log𝟐 𝟑 ≈ 𝒏 𝟏.𝟓𝟗 𝑻 𝒏 = 𝟑𝑻 𝒏 𝟐 + 𝚯 𝒏 𝒇 𝒏 = 𝒏 log𝟐 𝟑−𝜺 ,𝜺 ≈ 𝟎. 𝟓𝟗, ∴ 𝑻 𝒏 = 𝚯(𝒏 log𝟐 𝟑 ) = 𝚯(𝒏 𝟏.𝟓𝟗) 乘以2 n表示左移n位
矩阵乘法 两个nxn的矩阵A和B相乘 通常算法时间复杂性性为0(n23) 分治算法时间复杂度可降至0(n281 13
矩阵乘法 ◼ 两个 𝒏 × 𝒏 的矩阵 𝑨 和 𝑩 相乘 通常算法时间复杂性性为 𝚶(𝒏 𝟑 ) 分治算法时间复杂度可降至 𝚶(𝒏 𝟐.𝟖𝟏) 13
矩阵乘法 两个nxn的矩阵A和B相乘 a将A和B分成4个大小为×n的子矩阵运算 A11 412 B11 B12 21C22 2 21B22 C1=A1B1+A12B21,C12=A1B12+A12B2 C21=A21B1+A22B21,C22A21B12+A2B2 r(0=8r(2) +的(n a=8b=2,f(n)=6(n2),n9g28=n3 f(n)=ng28-,E= T(n)=6(ng28)=6 复杂性没有改善 14
矩阵乘法 ◼ 两个 𝒏 × 𝒏 的矩阵 𝑨 和 𝑩 相乘 将 𝑨 和 𝑩 分成 4 个大小为 𝒏 𝟐 × 𝒏 𝟐 的子矩阵运算 14 21 22 11 12 C C C C 21 22 11 12 A A A A 21 22 11 12 B B B B = C11=A11B11+A12B21，C12= A11B12+ A12B22 C21=A21B11+A22B21，C22= A21B12+ A22B22 复杂性没有改善 ∵ 𝒂 = 𝟖, 𝒃 = 𝟐, 𝒇 𝒏 = 𝚯 𝒏 𝟐 ,𝒏 log𝟐 𝟖 = 𝒏 𝟑 𝑻 𝒏 = 𝟖𝑻 𝒏 𝟐 + 𝚯 𝒏 𝟐 𝒇 𝒏 = 𝒏 log𝟐 𝟖−𝜺 ,𝜺 = 𝟏, ∴ 𝑻 𝒏 = 𝚯(𝒏 log𝟐 𝟖 ) = 𝚯(𝒏 𝟑 )
矩阵乘法 两个nxn的矩阵A和B相乘 a将A和B分成4个大小为×n的子矩阵运算 A11 412 B11 B12 21C22 2 21B22 将8个矩阵相乘转变成7个矩阵相乘 M1=A1(B12-B2 M2=(A1+A12)B22 Cu=M5+M-M2+ M3=(A21+A2)B1 C12=M1+M2 M4=A2B21-B1) C21=M3+M (A1+A2)(B1+ M5+M1-M3-M7 16=(412-A2)(B21+B2) =(A1-A21)(B1+B12 15
矩阵乘法 ◼ 两个 𝒏 × 𝒏 的矩阵 𝑨 和 𝑩 相乘 将 𝑨 和 𝑩 分成 4 个大小为 𝒏 𝟐 × 𝒏 𝟐 的子矩阵运算 15 21 22 11 12 C C C C 21 22 11 12 A A A A 21 22 11 12 B B B B = 将 8 个矩阵相乘转变成7 个矩阵相乘 M1 = A11 (B12 - B22) M2 = (A11 + A12) B22 M3 = (A21 + A22) B11 M4 = A22 (B21 - B11) M5 = (A11 + A22) (B11 + B22) M6 = (A12 - A22) (B21 + B22) M7= (A11 – A21) (B11 + B12) C11 = M5 + M4 - M2 + M6 C12 = M1 + M2 C21 = M3 + M4 C22 = M5 + M1 – M3 – M7