我绝对不会告诉你我是因为太蒻了，不会 FFT 才搞这个的。
我用一下别人的图没什么问题吧
看得懂吧？比如 X = 123456 , Y = 987654 X=123456,Y=987654 X=123456,Y=987654，则 n = 3 , A = 123 , B = 456 , C = 987 , D = 654 n=3,A=123,B=456,C=987,D=654 n=3,A=123,B=456,C=987,D=654。
前置知识：整数末端添 0 0 0 方法（不可能不会吧），就是乘 10 10 10，当然添 n n n 个零就是乘 1 0 n 10^n 10n， n 2 \frac{n}{2} 2n 个就是乘 1 0 n 2 10^{\frac{n}{2}} 102n。
失败……
接下来！
∵ X = A × 1 0 n 2 + B , Y = C × 1 0 n 2 + D \because X=A \times 10^{\frac{n}{2}} + B,Y=C \times 10^{\frac{n}{2}} + D ∵X=A×102n+B,Y=C×102n+D
∴ X × Y = ( A × 1 0 n 2 + B ) × ( C × 1 0 n 2 + D ) = A C × 1 0 n + A D × 1 0 n 2 + B C × 1 0 n 2 + B D = A C × 1 0 n + ( A D + B C ) × 1 0 n 2 + B D \therefore \begin{align*} X \times Y = &(A \times 10^{\frac{n}{2}} + B) \times (C \times 10^{\frac{n}{2}} + D) \\ = &AC \times 10^n + AD \times 10^{\frac{n}{2}} + BC \times 10^{\frac{n}{2}} + BD \\ = &AC \times 10^n + (AD+BC) \times 10^{\frac{n}{2}} + BD \end{align*} ∴X×Y===(A×102n+B)×(C×102n+D)AC×10n+AD×102n+BC×102n+BDAC×10n+(AD+BC)×102n+BD
需要进行 4 4 4 次乘法（ 1 0 k 10^k 10k 不算，因为是直接添 0 0 0）。
所以时间复杂度 T ( n ) = 4 T ( n 2 ) T(n) = 4T(\frac{n}{2}) T(n)=4T(2n)。
也就是一棵满四叉树，节点数很多，不过只需要关心最后一层。
最后一层有 4 k 4^k 4k 个节点， k k k 为高度（根节点其实为 0 0 0，但是其实都是细节，无伤风雅）， k = l o g 2 n k = log_2n k=log2n。
所以，时间复杂度为 O ( 4 l o g 2 n ) O(4^{log_2n}) O(4log2n)，也就是：
O ( 4 log 2 n ) = O ( ( 2 2 ) log 2 n ) = O ( 2 2 log 2 n ) = O ( ( 2 log 2 n ) 2 ) = O ( n 2 ) \begin{align*}\\ & O(4^{\log_2n}) \\ = & O((2^2)^{\log_2n})\\ = & O(2^{2\log_2n})\\ = & O((2^{\log_2n})^2) \\ = & O(n^2) \end{align*} ====O(4log2n)O((22)log2n)O(22log2n)O((2log2n)2)O(n2)
谔谔，为什么还是 O ( n 2 ) O(n^2) O(n2)，这反面原本一样吗ToT。
乐成
我们观察式子：
A C × 1 0 n + ( A D + B C ) × 1 0 n 2 + B D AC \times 10^n + (AD+BC) \times 10^{\frac{n}{2}} + BD AC×10n+(AD+BC)×102n+BD
发现它有三个部分，答案是这三个部分的和：
- A C × 1 0 n AC \color{grey}{\times 10^n} AC×10n 一次乘法
- ( A D + B C ) × 1 0 n 2 (AD+BC) \color{grey}{\times 10^{\frac{n}{2}}} (AD+BC)×102n 两次乘法
- B D × 1 0 0 BD \color{grey}{\times 10^0} BD×100 一次乘法
发现就是第二个部分乘法次数最多。
考虑将其优化。
直接优化（化简）：很难，想不出来。
但是，假如式子中用了 A C AC AC 或 B D BD BD，则不会增长乘法次数，因为有重复，可以记载下来。
简单起见，我们关注前半段： A D + B C AD+BC AD+BC，考虑将其变为 ? ? + A C + B D ??+AC+BD ??+AC+BD。
A D + B C − A C − B D = A ( D − C ) + B ( C − D ) = A ( D − C ) − B ( D − C ) = ( A − B ) ( D − C ) \begin{align*} \\ &AD+BC-AC-BD \\ = & A(D-C) + B(C-D) \\ = & A(D-C) - B(D-C) \\ = & (A-B)(D-C) \end{align*} ===AD+BC−AC−BDA(D−C)+B(C−D)A(D−C)−B(D−C)(A−B)(D−C)
现在，只需要进行一次乘法。最终公式：
A C × 1 0 n + ( ( A − B ) ( D − C ) + A C + B D ) × 1 0 n 2 + B D AC \times 10^n + ((A-B)(D-C)+AC+BD) \times 10^{\frac{n}{2}} + BD AC×10n+((A−B)(D−C)+AC+BD)×102n+BD
时间复杂度：
T ( n ) = 3 T ( n 2 ) = 3 log 2 n = ( 2 log 2 3 ) log 2 n = ( 2 log 2 n ) log 2 3 = n l o g 2 3 \begin{align*} \\ T(n)=&3T(\frac{n}{2}) \\ =&3^{\log_2n} \\ =&(2^{\log_23})^{\log_2n} \\ =&(2^{\log_2n})^{\log_23} \\ =&n^{log_23} \end{align*} T(n)=====3T(2n)3log2n(2log23)log2n(2log2n)log23nlog23
那么 log 2 3 \log_23 log23 大约是多少呢？ log 2 3 ≈ 1.585 \log_23 \approx 1.585 log23≈1.585。
那么到底是多少呢？来不严谨地大略估计一下：
假计划算机每秒可以执行 1 0 8 10^8 108 条指令。
则最大可以计算的位数为： n log 2 3 = 1 0 8 n^{\log_23} = 10^8 nlog23=108，则位数最大约为 111541 111541 111541。
而对比淳厚算法 O ( n 2 ) O(n^2) O(n2)，最大位数仅为 10000 10000 10000，相比之下多了一个多数量级！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
