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

Question

我编写了以下代码来查找字谜。我原以为这个的大 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

Answer 1

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 呢？

Answer 2

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

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

Big O notation of simple anagram function

python

big-o

time-complexity