给您一个字符串,例如"acdfdcqqc",需要创建一个算法来查找最大的回文子字符串,在我们的例子中是"cdfdc"。通过创建大小为2n的数组并每次计算以该点为中心的最大回文的长度(即:

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)吗?

最佳答案

算法的预期运行时间是算法在所有可能输入上的平均运行时间(见CLRS的第5章)正如教科书所指出的,解决这个问题并不总是容易的,有时使用另一种方法是有用的:算法在随机选择的输入上的运行时间。但原理是一样的:“预期运行时间”的概念是概率的,只适用于算法的大量应用。
相比之下,“最坏运行时间”是算法在任何输入(每个长度)上的最坏运行时间。这也不总是容易计算的,但是它可以进行最小上界计算,这在大o符号的情况下是很好的,因为o(f(n))只表示f(n)是上界。
如果对一组受限输入应用算法,则可以指定该受限集上的预期运行时间或最坏情况下的运行时间;如果输入在可能的输入范围内分布不均匀,则在计算预期运行时间时应将其考虑在内。
在回文长度的情况下,如果输入是随机选择的英文文本子串,最大回文的预期长度将(稍微)长于从整个字符串世界中随机选择的文本的最大回文的预期长度,这些字符串的字符是从小写字母和空格字符集中提取的。但对于这两组输入,最长回文的预期长度为O(1)。
因此,可以说您的算法是“预期的o(n)”,尽管您还应该指定输入字符串范围的性质。但是如果你不能控制算法的输入,那么最坏情况下的运行时间也是相关的,因为很容易为你的天真算法设计最坏情况下的输入,所以对它的dos攻击显然是可行的。

10-06 05:08
查看更多