给定两个大整数u和v,它们分别有m和n位数字,且m≤n.用通常的乘法求uv的值需要O（mn)时间.可以将u和v均看作有n位数字的大整数.用本章介绍的分治法,在O（mlog3)时间内计算iuv的值.当m比n小得多时,用这种方法就显得效率不够高.试设计一个算法,在上述情况下用O（nmlog3/2)时间求出uv的值.

首先，我们可以将 $u$ 和 $v$ 分别拆分成高位和低位两个部分，即：

$$
u = u_1 \times 10^{\lfloor \frac{n}{2} \rfloor} + u_0 \\
v = v_1 \times 10^{\lfloor \frac{n}{2} \rfloor} + v_0
$$

这样，$uv$ 就可以表示为：

$$
uv = (u_1 \times 10^{\lfloor \frac{n}{2} \rfloor} + u_0) \times (v_1 \times 10^{\lfloor \frac{n}{2} \rfloor} + v_0) \\
= u_1v_1 \times 10^n + (u_1v_0 + u_0v_1) \times 10^{\lfloor \frac{n}{2} \rfloor} + u_0v_0
$$

我们可以使用递归的方式来计算上述式子。具体地，我们可以先递归地计算 $u_1v_1$ 和 $u_0v_0$，然后再计算 $u_1v_0 + u_0v_1$。$u_1v_0 + u_0v_1$ 可以转化为 $(u_1 + u_0)(v_1 + v_0) - u_1v_1 - u_0v_0$，因此我们只需要递归地计算 $(u_1 + u_0)(v_1 + v_0)$，然后减去 $u_1v_1$ 和 $u_0v_0$ 即可。

这样，我们就可以得到一个 $O(n^{\log_2 3})$ 的算法。如果 $m$ 比 $n$ 小得多，我们可以将 $u$ 和 $v$ 都看作有 $n$ 位数字的大整数，然后使用上述算法计算 $uv$，这样可以得到一个 $O(n^{\log_2 3})$ 的时间复杂度。因此，总时间复杂度为 $O(n^{\log_2 3}) = O(m \cdot n^{\log_2 3 - 1}) = O(mn^{\frac{\log_2 9}{2}})$。