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

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

这取决于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的元素既不是全部相等，也不是全部唯一。

Answer 2

答案

假设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，而不是更小的，请参阅这个问题

<标题>重要提示顺便说一下，我想如果你使用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

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