这个算法寻找最长回文子串的时间复杂度是多少？

Question

下面是Python代码：

def is_palindrome(s):
    return s == s[::-1]


def longestp(s):
    if is_palindrome(s):
        return s

    maxp = s[0]

    for i in range(len(s)-1):
        half_length = len(maxp) // 2
        start = i - half_length
        end = i + half_length

        while start >= 0 and end <= len(s)-1:
            if is_palindrome(s[start:end+2]):
                if len(s[start:end+2]) > len(maxp):
                    maxp = s[start:end+2]
                end += 1
            elif is_palindrome(s[start:end+1]):
                if len(s[start:end+1]) > len(maxp):
                    maxp = s[start:end+1]
                start -= 1
                end += 1
            else:
                break

    return maxp

我最初认为它是O(n^3)，因为有两个嵌套的循环和字符串切片，但是在我的测试中它几乎是线性的。有没有什么输入，这个算法会比较慢？在

Answer 1

绝对不是线性的。尝试使用包含大量回文但不是回文的输入：

>>> timeit.timeit('longestp(x)', 'x="a"*100000+"b"', globals=globals(), number=1)
5.5123205203562975
>>> timeit.timeit('longestp(x)', 'x="a"*10000+"b"', globals=globals(), number=1)
0.08460151217877865

切片和s == s[::-1]比解释过的Python代码有更好的常量因子，您需要确保内部循环不会过早地break。你试图判断时间的复杂性可能已经被时间的影响所抛弃。在

---

我也不认为是O（n^3）。由于break条件，嵌套循环的交互方式与您的直觉预期不符。内环在算法的整个过程中执行O（n）次迭代，因为在有限的迭代次数之后，len(maxp)会增长，或者循环{}s。在我看来，这个算法是最差的O（n^2）。在

Answer 2

算法看起来好像需要的总时间与

integral_0^N x dx = [(x^2)/2]_0^N = (N^2)/2 = O(N^2)

匹配ab*的字符串应该给出最坏情况下的行为。在

下面是一段代码，它在实验中演示了最坏情况下的行为。在

结构如下：

1. 定义worstCase函数，该函数构造长度为N的“错误”字符串
2. 在这些字符串上测量函数的时间
3. 创建log(N)与log(time(N))的数据集
4. 拟合一条直线，试着估计直线的斜率：这是你的O(N^p)中的指数p。在

代码如下：

^{pr2}$

以下是输出（需要一两分钟）：

4800 -> 0.057818
5760 -> 0.078123
6908 -> 0.105169
8292 -> 0.145572
9952 -> 0.197657
11940 -> 0.276103
14332 -> 0.382668
17196 -> 0.534682
20636 -> 0.747468
24764 -> 1.048267
29720 -> 1.475469
35664 -> 2.081608
42796 -> 2.939904
51356 -> 4.216063
61628 -> 5.963550
73952 -> 8.691849
88744 -> 12.126039
106492 -> 19.684188
127788 -> 24.942766
Exponent was: 1.867208    

它估计指数为~1.86，接近2比接近3。在