位乘问题设XY是两个n位二进制n =2k求XY。试设计一个分治算法求解该位乘问题请给出求解过程的伪代码描述并对该算法在最差情况下的时间复杂度进行估计要求给出递推式及推导过程。给出正确的解答步骤

伪代码描述：

1. 若n=1，则直接返回X*Y。
2. 将X和Y分别拆分为高位和低位两部分，即X = X_h * 2^(n/2) + X_l，Y = Y_h * 2^(n/2) + Y_l。
3. 递归地求解四个子问题： a. Z_0 = X_l * Y_l b. Z_1 = (X_h + X_l) * (Y_h + Y_l) c. Z_2 = X_h * Y_h
4. 计算结果为 Z = Z_2 * 2^n + (Z_1 - Z_2 - Z_0) * 2^(n/2) + Z_0。
5. 返回Z作为XY的乘积。

时间复杂度的估计： 在最差情况下，每次求解子问题的时间复杂度为T(n/2)，因此递推式为T(n) = 3T(n/2) + O(n)。 根据主定理，可得到T(n) = O(n^log2(3))。