回文测试的复杂性

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），因为每个调用都有一个（最坏的情况下）O（n）slice有n个电话。

哪一个是正确的？

来源

2014-06-11 Frank Epps

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

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

来源

2014-06-11 02:04:43

你的最后一笔是'为O（n^2）'，'不为O（n）'。 – arshajii

你是说O（n^2）吗？谢谢！ –

@arshajii - 谢谢 - 对我来说这没有任何意义。 –

回文测试的复杂性

回答

相关问题