回文测试的复杂性

Question

def is_palindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])

我最开始的想法是，这个复杂度是 O(n)，因为每次递归调用都会去掉 2 个字符。

但后来我想到了切片的复杂度。根据 这个链接，获取一个切片的复杂度是 O(k)，其中 k 是切片中的元素数量。在 is_palindrome 函数中，k = n - 2，然后是 k = n - 4，再然后是 n - 6，等等。所以我觉得复杂度应该是 O(n^2)，因为每次调用的切片在最坏情况下是 O(n)，而且总共有 n 次调用。

那么，哪个说法是正确的呢？

Answer 1

想象一下你有一个经典的 O(n^2) 算法：双重嵌套的 for 循环。

for i in range(n):
    for j in range(n):
        #do_something

在外层循环的每一次迭代中，内层循环 O(n) 也必须执行一次。这就导致了 O(n^2) 的运行时间。

现在我们来看看你的算法——在每一层递归中，都会调用另一个 O(n) 的算法（你的切片操作）。你的递归函数就像外层循环，而你的切片函数就像内层循环。

你的递归函数是

O(n/2) => O(n)

而你的切片函数是

O(t) where t < n 

判断一个字符串是否是回文的另一种 O(n) 的方法是，只需遍历字符串一次，并在每次迭代中检查列表的两端。记住，索引访问是 O(1) 的。

for i in xrange(len(s)/2):
  if s[i] != s[(len(s)-1)-i]:
    return False
return True