简介
给与两个比较大的数X和Y，且不能直接用基本类型表示，利用分治思想将X、Y分别拆分为A与B、C与D(长度不同可以补0)。
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
X*Y = (A*10^\frac{n}{2}+B) (C*10^\frac{n}{2}+D) \\ = A*C*10^n + A*D*10^\frac{n}{2}+B*C*10^\frac{n}{2}+B*D
X?Y=(A?102n?+B)(C?102n?+D)=A?C?10n+A?D?102n?+B?C?102n?+B?D
而AC, AD,BC,BD再通过分治法求解，乘以10的幂相当于移位操作。所以需要调用四次分治乘法函数，所以时间复杂度为：
T
(
n
)
=
4
?
T
(
n
2
)
+
θ
(
n
)
T(n) = 4*T(\frac{n}{2})+\theta (n)
T(n)=4?T(2n?)+θ(n)
通过master定理可得
T
(
n
)
=
θ
(
n
2
)
T(n)=\theta (n^2)
T(n)=θ(n2)。
通过化简上述公式得
X
?
Y
=
A
?
C
?
1
0
n
+
(
A
?
D
+
B
?
C
?
)
1
0
n
2
+
B
?
D
=
A
?
C
?
1
0
n
+
(
(
A
?
B
)
?
(
D
?
C
)
+
A
?
C
+
B
?
D
)
?
1
0
n
2
+
B
?
D
X*Y = A*C*10^n + (A*D+B*C*)10^\frac{n}{2}+B*D\\ = A*C*10^n + ((A-B)*(D-C)+A*C+B*D)*10^\frac{n}{2}+B*D
X?Y=A?C?10n+(A?D+B?C?)102n?+B?D=A?C?10n+((A?B)?(D?C)+A?C+B?D)?102n?+B?D
可知只需要对AC，DB, (A-B)*(D-C)再通过分治法求解, 所以只需要调用三次分治乘法函数即可,所以时间复杂度为:
T
(
n
)
=
3
?
T
(
n
2
)
+
θ
(
n
)
T(n) = 3*T(\frac{n}{2})+\theta (n)
T(n)=3?T(2n?)+θ(n)
通过master定理可得
T
(
n
)
=
θ
(
n
l
o
g
2
3
)
T(n)=\theta (n^{{log_23}})
T(n)=θ(nlog2?3)。
参考
分治法的经典问题——大整数相乘
【算法】大数乘法问题及其高效算法
|