时间戳

首页 > 解决方案 > python函数的时空复杂度

python - python函数的时空复杂度

问题描述

你能帮我计算一下下面代码的空间和时间复杂度吗

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

标签： pythonstringtime-complexitybig-ospace-complexity

解决方案

该功能可以分解为其子过程的复杂性。在计算这个时间复杂度时，让 Python 术语中的字符数string为n ( n = len(string)。现在，让我们看一下 2 个子流程：

  1. string以相反的顺序遍历所有字符并分配给string1（这是通过string1=string[::-1]） - O(n)线性时间，因为 中有n 个字符string。
  2. 比较 if string1 == string- O(n)线性时间，因为每个字符串中的 n 个字符将相互比较，因此是n一对一比较。

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

推荐阅读