python函数的时空复杂度

Question

您能告诉我如何计算下面代码的空间和时间复杂度吗

def isPalindrome(string):
# Write your code here.
string1=string[::-1]
if string1==string:
return True
else :
return False

Answer 1

查找复杂性最简单的方法是逐行查看每个操作。

我们从第一行

开始

string1=string[::-1]

这是一个字符串切片操作，它将字符串反转，根据这一点，它所需的时间与被复制的字符数量成正比，在这种情况下(你的代码)它是整个字符串，因此它将是O(n)这是第一行。让我们继续

if string1==string:

这里我们在if语句的条件部分进行字符串比较。据此，对于第2行

，又是O(n)现在，下面的行只是返回和else块，将在常量时间内完成，即O(1)

因此，对于总复杂度，我们只需将所有行的复杂度相加。即O(n) + O(n) + O(1) + O(1)

你可以参考这个来学习如何简化它。

所以最终的时间复杂度为O(n)

Answer 2

该函数可以分解为其子过程的复杂性。在计算这个时间复杂度时，设string中的字符数量为n(Python术语中的n = len(string)。现在，让我们看看这两个子进程:

1. 按反向顺序遍历string中的所有字符并分配给string1(这是由string1=string[::-1]完成的)-O(n)由于string中有n个字符，所以时间是线性的。
2. 比较string1 == string-0 (n)线性时间，因为每个字符串中的n个字符将相互比较，所以是n1对1比较。

因此，总时间复杂度为O(n) + O(n)其中n为len(string)。简而言之，我们将其简化为O(n)复杂度.

Answer 3

以下两个操作决定了上述代码的时间复杂度:

1. 使用下面的操作，您将以相反的方式创建列表的副本，这需要O(n)时间和O(n)空间:

   string1 = string[::-1]
   

2. 检查下一行中的字符串是否相等再次使用O(n)操作，因为您需要在最坏的情况下比较所有字符:

   if string1==string:
   

综上所述，我们可以得出如下结论:

时间复杂度:O(n)

空间复杂度:O(n)

其中n表示输入字符串的长度。

你也会喜欢阅读这个文档，它总结了Python中不同操作的时间复杂性。