简单字谜函数的大 O 表示法

Big O notation of simple anagram function

我编写了以下代码来查找字谜。我原以为这个的大 O 符号是 O(n) 但我的老师告诉我我错了。我很困惑为什么这是不正确的,但是有人能提供任何建议吗?

# Define an anagram.
def anagram(s1, s2):
    return sorted(s1) == sorted(s2)

# Main function.
def Question1(t, s):
    # use built in any function to check any anagram of t is substring of s
    return any(anagram(s[i: i+len(t)], t)
                 for i in range(len(s)-len(t)+ 1))

函数调用:

# Simple test case.
print Question1("app", "paple")
# True

any anagram of t is substring of s

这不是您的代码所说的。

你有 "any substring of s is an anagram of t",这可能是等价的,但这样更容易理解。


至于复杂度,你需要定义你所说的N...是len(s)-len(t)+ 1吗?

函数any()的复杂度为N,那么是的。

但是,您还对 T 长度的输入调用了 anagram,而您似乎忽略了这一点。

anagram 调用了 sorted 两次。假设合并排序,对 sorted 的每次调用都更接近 O(T * log(T)) 本身。您还在执行列表切片,因此它可能会稍微高一些。

假设您的复杂度约为 (S-T) * 2 * (T * log(T)),其中 T 和 S 是字符串的长度。

答案取决于您输入的字符串较大。

最好的情况是它们的长度相同,因为那样你的范围只有一个元素。

虽然大 O 表示法是最坏的情况,因此您需要弄清楚哪些条件会在总操作方面产生最大的复杂性。例如,如果 T > S 怎么办?那么 len(s)-len(t)+ 1 将是非正数,那么代码 运行 是多于还是少于等长字符串?那么 S < T 或 S = 0 呢?

由于一些因素,这不是 N 复杂性。第一个 sorted 具有 O(n log n) 复杂度。如果 T 足够长,您可能可以调用它几次(并对 T 和 S 进行排序)。