回文分割回溯解法O(N*2^N)时间复杂度推导相关问题

我们默认讨论最坏情况：输入字符串所有字符相同（如aaaaa...），此时任意子串都是回文，没有剪枝，所有分割方案都会被遍历到。

递推式建立 #

设T(n)为处理长度为n的剩余字符串的总时间开销：

• 边界条件：T(0) = O(1)，空串时直接将当前分割结果加入答案，常数开销
• 对长度为n的非空串：
  我们需要枚举第一个分割块的长度l（范围1~n），每次枚举做两个操作：
  1. 校验长度为l的前缀是否为回文，开销为O(l)
  2. 递归处理剩下长度为n-l的子串，开销为T(n-l)
     因此递推式为：

  T(n) = Σ (l=1到n) [O(l) + T(n-l)]

递推式化简求解 #

将求和项拆分：
T(n) = Σ(l=1到n)O(l) + Σ(l=1到n)T(n-l)

• 第一部分Σ(l=1到n)l = O(n²)
• 第二部分将变量替换为k = n-l，得到Σ(k=0到n-1)T(k)
  因此可以得到：
  T(n) = O(n²) + Σ(k=0到n-1)T(k)
  我们再写n-1对应的递推式做差消去求和项：
  T(n-1) = O((n-1)²) + Σ(k=0到n-2)T(k)
  两式相减得：
  T(n) - T(n-1) = O(n) + T(n-1)
  整理得最终递推关系：
  T(n) = 2*T(n-1) + O(n)
  这个递推式的解为O(n*2^n)，可以通过展开递推验证：
  T(n) = O(n) + 2*O(n-1) + 2²*O(n-2) + ... + 2^{n-1}*O(1)
  对这个求和式做错位相减计算，即可得到最高量级为n*2^n。

直观验证方法 #

你也可以换个角度快速估算：

• 总共有2^{n-1}种合法分割方案
• 每个分割方案平均包含O(n)个回文子串
• 每个子串的回文校验开销和长度成正比，所有分割方案的所有子串总长度之和的量级为O(n*2^n)，和递推结果一致。
  另外你代码中curr + [chunk]的列表拼接操作开销也是和当前curr的长度成正比，这部分总开销同样是O(n*2^n)，不会改变最高时间复杂度量级。

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