求最大回文子串，算法复杂度
Find largest palindromic substring, algorithm complexity
给你一个字符串，例如"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) 吗？
没有
在算法设计中，说算法在预期的 O(n) 时间内运行意味着它对每个可能的输入。也就是说，期望应该基于算法的随机性（内部抛硬币），而不是基于从受限集中随机均匀选择输入的事实。
但是，并不代表你的算法不好。可以使用输入仅限于英文文本这一事实，因此具有使算法比一般输入更快的某些属性。但是您使用的术语（预计 O(n) 时间）是为每个输入的 运行 时间预计为 O(n) 的算法保留的。
算法的预期 运行 时间是算法对所有可能输入的平均 运行 时间。 （请参阅 CLRS 的第 5 章。）正如教科书所指出的，解决这个问题并不总是那么容易，有时使用替代方法很有用：算法的 运行 时间随机选择的输入。但原理是一样的："expected running-time"的概念是概率的，只适用于聚合算法的大量应用。
相比之下，"worst-case running-time" 是算法在任何输入（每个长度）上最差的 运行 时间。这也并不总是容易计算，但它适用于最小上限计算，这在大 O 表示法的情况下很好，因为 O(f(n)) 只表示 f(n) 是一个上限绑定。
如果您将算法应用于一组受限制的输入，您可以指定预期或最坏情况下的 运行-时间；如果输入未均匀分布在可能的输入范围内，则在计算预期 运行 时间时应考虑到这一点。
在回文长度的情况下，如果输入是随机选择的英文文本子串，则最大回文的预期长度将（略）长于随机选择的文本的最大回文的预期长度来自整个字符串世界，其字符取自小写字母集和 space 字符。但是对于这两组输入，最长回文的预期长度是 O(1)。
所以可以说你的算法是"expected O(n)"，尽管你还应该指定输入字符串范围的性质。但是如果你不能控制算法的输入，最坏情况 运行 时间也是相关的，因为很容易为你的天真算法设计最坏情况输入，所以对它的 DoS 攻击显然是可行。
给你一个字符串，例如"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) 吗？
没有
在算法设计中，说算法在预期的 O(n) 时间内运行意味着它对每个可能的输入。也就是说，期望应该基于算法的随机性（内部抛硬币），而不是基于从受限集中随机均匀选择输入的事实。
但是，并不代表你的算法不好。可以使用输入仅限于英文文本这一事实，因此具有使算法比一般输入更快的某些属性。但是您使用的术语（预计 O(n) 时间）是为每个输入的 运行 时间预计为 O(n) 的算法保留的。
算法的预期 运行 时间是算法对所有可能输入的平均 运行 时间。 （请参阅 CLRS 的第 5 章。）正如教科书所指出的，解决这个问题并不总是那么容易，有时使用替代方法很有用：算法的 运行 时间随机选择的输入。但原理是一样的："expected running-time"的概念是概率的，只适用于聚合算法的大量应用。
相比之下，"worst-case running-time" 是算法在任何输入（每个长度）上最差的 运行 时间。这也并不总是容易计算，但它适用于最小上限计算，这在大 O 表示法的情况下很好，因为 O(f(n)) 只表示 f(n) 是一个上限绑定。
如果您将算法应用于一组受限制的输入，您可以指定预期或最坏情况下的 运行-时间；如果输入未均匀分布在可能的输入范围内，则在计算预期 运行 时间时应考虑到这一点。
在回文长度的情况下，如果输入是随机选择的英文文本子串，则最大回文的预期长度将（略）长于随机选择的文本的最大回文的预期长度来自整个字符串世界，其字符取自小写字母集和 space 字符。但是对于这两组输入，最长回文的预期长度是 O(1)。
所以可以说你的算法是"expected O(n)"，尽管你还应该指定输入字符串范围的性质。但是如果你不能控制算法的输入，最坏情况 运行 时间也是相关的，因为很容易为你的天真算法设计最坏情况输入，所以对它的 DoS 攻击显然是可行。