分治法求最长公共前缀的时间复杂度推导疑问

算法回顾 #

分治法求n个字符串的最长公共前缀（LCP）步骤：

• 递归拆分：将n个字符串分成两组（各约n/2个），直到每组仅含1个字符串，此时前缀为字符串本身。
• 合并求解：将两组的LCP再求一次LCP，返回给上一级。

疑问1：递归式T(n) = 2T(n/2) + O(m)的时间复杂度计算 #

首先明确递归式中各项的含义：

• T(n)：处理n个字符串的总时间
• 2T(n/2)：拆分后处理两组子问题的时间
• O(m)：合并两个子组LCP的时间（最多需对比m个字符）

手动展开递归式求解

逐层展开递归式：

T(n) = 2T(n/2) + O(m)
= 2*(2T(n/4) + O(m)) + O(m) = 4T(n/4) + 2*O(m) + O(m)
= 8T(n/8) + 4*O(m) + 2*O(m) + O(m)
...
直到拆分到每组1个字符串，此时n/(2^k) = 1 → k = log₂n

最终展开结果：

T(n) = 2^k * T(1) + O(m)*(2⁰ + 2¹ + ... + 2^{k-1})

代入2^k = n，且T(1)=O(m)（单个字符串的前缀是自身，需O(m)时间确认），同时等比数列求和2⁰+2¹+...+2^{k-1}=n-1：

T(n) = n*O(m) + O(m)*(n-1) = O(mn) + O(mn) = O(mn)

关于主定理的适用性

主定理的标准形式针对单变量n的递归关系，而这里的O(m)是与n无关的参数（字符串平均长度）。若强行套用主定理，a=2, b=2, log_b a=1，f(n)=O(m)=O(1)属于O(n^0)，满足主定理情况1（f(n)=O(n^{log_b a - ε}), ε>0），会得到T(n)=Θ(n)，但这是将m视为常数的结果。实际上我们需要考虑m和n两个变量，因此手动展开更准确，最终时间复杂度为O(mn)。

疑问2：自行推导的合理性验证 #

你的推导是合理的，具体解释如下：
最坏情况下，每一层的合并操作都需要对比到第m个字符：

• 最深层（基准层）：共n个字符串，总字符数为m*n
• 上一层：共n/2组合并，每组对比m个字符，总字符数为m*(n/2)
• 再上一层：共n/4组合并，总字符数为m*(n/4)
• ...
• 最顶层：1组合并，总字符数为m*1

总工作量为等比数列求和：

m*n + m*(n/2) + m*(n/4) + ... + m*1 = m*n*(1 + 1/2 + 1/4 + ...)

等比数列1+1/2+1/4+...的极限为2，因此总工作量为2mn，忽略常数系数后时间复杂度为O(mn)，和递归式推导结果一致。

内容的提问来源于stack exchange，提问作者Helen Guo