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

Question

我对以下代码的时间复杂度感到困惑，我需要所有能得到的帮助，因为我正在努力弄清楚它。

代码如下：

def herhalen(s,p):
    pc = 0
    while pc < len(s):
       pd = pc + 1
       while pd < len(s):
          if s[pd] == s[pc]:
             x = 0
             while pd + x < len(s) and x < p and s[pc + x] == s[pd + x]:
                x += 1
             if x ==p:
                return True
          pd += 1
       pc += 1
    return False

Answer 1

回答

我们假设 N 是 len(s)

外循环具有 O(N) 的复杂性，因为 pc 需要从 0 到 len(s) - 1 的所有值。第二个循环具有相同的复杂度：虽然 pd 从 pc + 1 开始，而不是从 0 开始，但两个循环加起来的复杂度将是 O(N * N / 2) = O(N^2)。内部循环将具有 O(min(N, P)) 复杂性（其中 P 是函数中的 p 变量），因为循环将在 pd + x 达到 len(s) 或当 x 达到 p

所以，假设P不是太小，如果我没记错的话，整体复杂度是O(N^3)

如果您难以理解为什么内部循环（从可迭代的外部循环开始而不是 0）将复杂度乘以 N，而不是更小的东西，请参阅 this question

重要提示

顺便说一下，如果您使用 for 循环而不是 while，我想您自己理解复杂性会容易得多。我将按以下方式重写代码（也包含一些小的样式改进）：

def herhalen(s, p):
    for pc in range(len(s)):
       for pd in range(pc + 1, len(s)):
          if s[pd] == s[pc]:
             for x in range(p):
                 if pd + x < len(s) or s[pc + x] == s[pd + x]:
                     break
             else:
                return True
    return False

使用您正在编写的语言的所有功能:)

Answer 2

这取决于s的元素。例如，如果 s 的所有元素都相等，那么您的条件 if s[pd] == s[pc] 将始终为真，这反过来会影响整体复杂性。然而，如果 s 的所有元素都是不同的，那么 s[pd] == s[pc] 只有在 pd 和 pc 保持相同的值并因此指向相同的元素时才为真s.

示例 1 - 唯一元素

s = [i for i in range(20)] #[0,1,2,...,19]
pc = 0
while pc < len(s):
    pd = pc + 1
    while pd < len(s):
        if s[pd] == s[pc]:
            print(pd)
        pd += 1
    pc += 1

在这种情况下，print 函数永远不会执行。

示例 2 - 相同的元素

s = [0 for i in range(20)] #[0,0,...,0]
pc = 0
print_counter = 1
while pc < len(s):
    pd = pc + 1
    while pd < len(s):
        if s[pd] == s[pc]:
            print(print_counter)
            print_counter += 1
        pd += 1
    pc += 1

在这种情况下，print 函数执行了 190 次，即 O(n^2)。

备注

请注意，对于您的代码，您必须考虑一个额外的循环。
另请注意，存在更多 s 的元素既不完全相等也不完全唯一的情况。

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

What time complexity does the following code have?

python

complexity-theory

time-complexity

spyder

回答

重要提示

示例 1 - 唯一元素

示例 2 - 相同的元素

备注