回文测试的复杂性 [英] Complexity of palindrome test

问题描述

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

我的第一个想法是复杂度是 O(n)，因为每次递归调用都会删除 2 个字符.

My first thought was that the complexity is O(n) because each recursive call removes 2 characters.

但后来我想到了切片的复杂性.根据 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 次调用.

But then I thought of the slice's complexity. According to https://wiki.python.org/moin/TimeComplexity, the complexity of getting a slice is O(k), where k = number of elements in the slice. In is_palindrome, k = n - 2, then k = n - 4, then n - 6, etc. so I thought the complexity would be O(n^2) because each call has an (at worst) O(n) slice and there are n calls.

哪个是正确的?

推荐答案

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

Imagine you have the classic O(n^2) algorithm: the double nested for-loop

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

对于外循环的每次迭代，必须执行内循环的整个迭代O(n).这导致 O(n^2) 运行时.

For every iteration of the outer loop, an entire iteration of the inner loop O(n) must be executed. This results in an O(n^2) runtime.

现在让我们看看你的算法——对于每一级递归，必须调用另一个 O(n) 算法(你的切片)——你的递归函数类似于外循环，并且你的切片函数类似于内循环.

Now let's take a look at your algorithm - for every level of recursion, another O(n) algorithm (your slice) must be called - your recursive function is analogous to the outer loop, and your slice function is analogous to the inner loop.

你的递归函数是

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

你的切片功能是

O(t) where t < n 

另一种确定字符串是否为回文的O(n) 方法是简单地迭代字符串一次，并在每次迭代中检查列表的两端.记住索引访问是O(1)

An alternate O(n) way to decide whether a string is palindrome is to simply iterate over the string once and in each iteration check opposite ends of the list. Remember the index accesses are O(1)

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

这篇关于回文测试的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！