python - 回文测试的复杂性

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 个字符。

但后来我想到了切片的复杂性。根据https://wiki.python.org/moin/TimeComplexity ，获取切片的复杂度为 O(k)，其中 k = 切片中的元素数量。在 is_palindrome 中，k = n - 2，然后 k = n - 4，然后 n - 6 等等，所以我认为复杂度是 O(n^2) 因为每个调用都有一个 (at最坏)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