use*_*275 2 algorithm dynamic-programming palindrome
您将获得一个字符串,例如"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个可能的起点中的每一个,我在两个方向上移动,找到从该位置开始的最大回文的长度.因此,对于我在大多数O(n)操作中执行的2n个操作中的每一个,因此O(n ^ 2)时间复杂度.
我知道它可以使用发烧友算法在线性时间内完成:https://en.wikipedia.org/wiki/Longest_palindromic_substring.
但假设我们处理的字符串是从自然英文文本中提取的.如果我们在英文文本中随机选择一个位置,那么我们可能期望找到的预期对称性非常低.我甚至会说,预期的对称性在每一方都不到一个字符.因此,我可以说我的算法正在进行2n次预期的恒定时间操作,使得算法平均值为O(n)吗？
没有.
在算法设计中,假设算法在预期O(n)时间内运行意味着它对每个可能的输入都这样做.也就是说,期望应该是算法的随机性(内部硬币翻转),而不是从限制集中随机均匀地选择输入的事实.
但是,这并不意味着您的算法不好.可以使用输入仅限于英文文本的事实,因此拥有某些属性使得算法比一般输入更快.但是您正在使用的术语(预期O(n)时间)保留给运算时间预计O(n)在每个输入上的算法.