问题描述
限时送ChatGPT账号..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/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/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屋!
更多推荐
[db:关键词]
发布评论