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

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

标签： pythontime-complexityspydercomplexity-theory

Answer 1

回答

假设N是len(s)

外部循环具有O(N)复杂性，因为从topc获取所有值。第二个循环具有相同的复杂性：虽然从 开始，而不是从开始，但两个循环一起将具有复杂性。内部循环将具有复杂性（函数中的变量在哪里），因为循环将在到达时或到达时结束0len(s) - 1pdpc + 10O(N * N / 2) = O(N^2)O(min(N, P))Pppd + xlen(s)xp

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

如果您难以理解为什么内部循环（从可迭代的外部循环而不是 开始0）将复杂性乘以N，而不是更小的东西，请看这个问题

重要的提示

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

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

使用你所写语言的所有力量:)