这个天真的解决方案的关键是什么？

Question

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

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)。

这个天真的解决方案的关键是什么？

What is the Big O of this naive solution?

python

big-o

time-complexity