下面的python代码的时间复杂度是多少？

Question

下面是在python中从字符串中删除循环字母的代码。我想知道这个代码的时间复杂度。更具体地说，行if string_1[i] not in char_found:的时间复杂度。在列表中搜索。你知道吗

如果可能的话，也可以用列表分配的空间来解释。你知道吗

def remove_recorring_char(string_1):
    result = ""
    char_found = []
    for i in range(0,len(string_1)):
        if string_1[i] not in char_found:
            char_found.append(string_1[i])
            result = result+string_1[i]
    return result

if __name__== "__main__":
    print(remove_recorring_char("aabbbcc"))
    print(remove_recorring_char("chdsgdsgggsggsjddaaxcvcj"))

Answer 1

if string_1[i] not in char_found:

这条线有两个作用：

首先，它访问string_1[i]。这需要固定的时间，因为字符串基本上只是字符数组。你知道吗

然后它在列表char_found中搜索，将该字符string_1[i]与每个元素进行比较，直到有一个匹配为止。这需要（最坏情况下）长度为char_found的线性时间。而且，由于char_found可能（最坏情况）是string_1[:i]中的所有字符，因此string_1的长度是线性的。你知道吗

所以，这一行是O(N)。你知道吗

当然，这条线在一个外循环中，更明显的是O(N)：for i in range(0,len(string_1)):。所以，这两者的结合就是O(N**2)。你知道吗

即使您将in测试修复为常数时间，您也可以在循环内执行result = result+string_1[i]。字符串串联在字符串长度上是最坏情况下的线性连接。CPython和PyPy的最新版本有一些优化，所以有时它是按固定时间分摊的，比如附加到列表中，但是Python语言不能保证这些优化。而result是，最坏的情况，也是只要string_1。所以，整个过程仍然是O(N**2)，除非你的解释器特别好。你知道吗

---

您可以通过做两个小的更改将整个过程简化为O(N)。你知道吗

首先，对char_found使用set而不是list。搜索一个集合，并添加到它，都是摊销常数时间操作。你知道吗

第二，对result使用list而不是str，然后在末尾使用result = ''.join(result)。附加到列表的时间是按固定时间摊销的。将一个列表转换回一个字符串当然是线性时间，但是你不能在循环中这样做，所以这很好。你知道吗