大蓬数乘法 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位