algorithm - 求最大回文子串，算法复杂度

Question

给你一个字符串，例如"acdfdcqqc" 并且需要创建一个算法来找到最大的回文子串，在我们的例子中是 "cdfdc"。通过创建一个大小为 2n 的数组并每次计算以该点为中心的最大回文的长度，很容易设计出 O(n^2) 算法，即:

a  -  c  -  d  -  f  -  d  -  c  -  q  -  q  -  c
1  0  1  0  1  0  5  0  1  0  1  0  1  4  1  0  1

对于 2n 个可能的起点中的每一个，我都在两个方向上移动，找到从该位置开始的最大回文的长度。因此，对于 2n 个操作中的每一个，我最多执行 O(n) 个操作，因此时间复杂度为 O(n^2)。

我知道可以使用更高级的算法在线性时间内完成:https://en.wikipedia.org/wiki/Longest_palindromic_substring .

但假设我们处理的字符串是从自然英文文本中提取出来的。如果我们在英文文本中随机选择一个位置，我们可能期望找到的预期对称性非常低。我什至会说预期的对称性在每一侧都少于一个字符。因此，我可以说我的算法正在执行 2n 次预期的恒定时间操作，使算法平均为 O(n) 吗？

Answer 1

没有。

在算法设计中，说一个算法按预期运行O(n) time 意味着它对每个可能的输入都这样做。。也就是说，期望应该基于算法的随机性(内部抛硬币)，而不是基于从受限集中随机均匀选择输入的事实。

但是，并不代表你的算法不好。可以使用输入仅限于英文文本这一事实，因此具有使算法比一般输入更快的某些属性。但是您使用的术语(预计 O(n) 时间)是为运行时间预计为 O(n) 的算法保留的。在每个输入上。