python - 这个天真的解决方案的大 O 是什么？

Question

这是一个接受两个输入字符串的简单函数。如果第二个字符串是第一个字符串的变位词，则返回 True。

def validAnagram(str1, str2):
    if len(str1) != len(str2):
        return False

    str1_arr = [char for char in str1]
    str2_arr = [char for char in str2]

    for char in str1_arr:
        if char in str2_arr:
            str2_arr.remove(char)
        else:
            return False
    return True

我正在学习计算我编写的程序的大 O。这个函数的运行时间是 O(N ² ) 还是 O(N ³ )？

我假设它的 O(N ³ )，因为“if”条件也运行 O(N)。所以它的 3 个嵌套 O(N) 操作，导致 O(N ³ ) 运行时。如果我错了，请纠正我。

Answer 1

它是O(N^2)。您有O(N)迭代，在其中执行O(N)操作。这导致O(N^2)总体上的复杂性。

我认为你错了计算这部分是O(N^2)，而实际上是O(N)：

    if char in str2_arr:
        str2_arr.remove(char)

因为你在O(N) + O(N)这里，它仍然只是O(N)。