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

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）。在