位乘问题分治算法求解及时间复杂度分析

"位乘问题"设X,Y是两个n位二进制，n =2k，求XY。试设计一个分治算法求解该位乘问题，请给出求解过程的伪代码描述，并对该算法在最差情况下的时间复杂度进行估计(要求给出递推式及推导过程)。\n\n给出正确的解答步骤内容：\n\n伪代码描述：\n\n1. 若n=1，则直接返回X*Y。\n2. 将X和Y分别拆分为高位和低位两部分，即X = X_h * 2^(n/2) + X_l，Y = Y_h * 2^(n/2) + Y_l。\n3. 递归地求解四个子问题：\n a. Z_0 = X_l * Y_l\n b. Z_1 = (X_h + X_l) * (Y_h + Y_l)\n c. Z_2 = X_h * Y_h\n4. 计算结果为 Z = Z_2 * 2^n + (Z_1 - Z_2 - Z_0) * 2^(n/2) + Z_0。\n5. 返回Z作为XY的乘积。\n\n时间复杂度的估计：\n在最差情况下，每次求解子问题的时间复杂度为T(n/2)，因此递推式为T(n) = 3T(n/2) + O(n)。\n根据主定理，可得到T(n) = O(n^log2(3))。