这段代码的大 O 表示法是什么?
What will be the big-O notation for this code?
它会是 O(n) 还是更大?
n
= 列表长度
a
是一个很长的整数列表
final_count=0
while(n>1):
i=0
j=1
while(a[i+1]==a[i]):
i=i+1
j=j+1
if i==n-1:
break
for k in range(j):
a.pop(0)
final_count=final_count+j*(n-j)
n=n-j
在我看来,如果没有 a.pop(0)
部分,您的代码 会 为 O(n)。由于列表是在内存中作为数组实现的,因此删除顶部的元素意味着数组中的所有元素也需要移动。所以从列表中删除是 O(n)。你在 j
的循环中这样做,据我所知,最后,所有 j
的总和将与 n
相同,所以你要删除项目 n
次,使这部分成为二次方 (O(n²))。
您可以通过不修改列表并仅跟踪初始索引来避免这种情况。这不仅消除了对 pop 的需要,而且消除了 j
上的循环,使复杂度计算更加直接:
final_count = 0
offset = 0
while n > 1:
i = 0
j = 1
while a[offset + i + 1] == a[offset + i]:
i += 1
j += 1
if i == n - 1:
break
offset += j
final_count += j * (n - j)
n = n - j
顺便说一句。我不太清楚为什么你每次都要跟踪 j
,因为 j = i + 1
,所以你可以去掉它,使代码更简单一些。最后 j * (n - j)
正好是 j * n
如果你 先 调整 n
:
final_count = 0
offset = 0
while n > 1:
i = 0
while a[offset + i + 1] == a[offset + i]:
i += 1
if i == n - 1:
break
offset += i + 1
n = n - (i + 1)
final_count += (i + 1) * n
最后一点:您可能会注意到,offset
现在从零开始计算到列表的长度,而 n
则相反,从列表的长度开始计算到零。你可以把它结合起来,所以你不需要两者。
它会是 O(n) 还是更大?
n
= 列表长度
a
是一个很长的整数列表
final_count=0
while(n>1):
i=0
j=1
while(a[i+1]==a[i]):
i=i+1
j=j+1
if i==n-1:
break
for k in range(j):
a.pop(0)
final_count=final_count+j*(n-j)
n=n-j
在我看来,如果没有 a.pop(0)
部分,您的代码 会 为 O(n)。由于列表是在内存中作为数组实现的,因此删除顶部的元素意味着数组中的所有元素也需要移动。所以从列表中删除是 O(n)。你在 j
的循环中这样做,据我所知,最后,所有 j
的总和将与 n
相同,所以你要删除项目 n
次,使这部分成为二次方 (O(n²))。
您可以通过不修改列表并仅跟踪初始索引来避免这种情况。这不仅消除了对 pop 的需要,而且消除了 j
上的循环,使复杂度计算更加直接:
final_count = 0
offset = 0
while n > 1:
i = 0
j = 1
while a[offset + i + 1] == a[offset + i]:
i += 1
j += 1
if i == n - 1:
break
offset += j
final_count += j * (n - j)
n = n - j
顺便说一句。我不太清楚为什么你每次都要跟踪 j
,因为 j = i + 1
,所以你可以去掉它,使代码更简单一些。最后 j * (n - j)
正好是 j * n
如果你 先 调整 n
:
final_count = 0
offset = 0
while n > 1:
i = 0
while a[offset + i + 1] == a[offset + i]:
i += 1
if i == n - 1:
break
offset += i + 1
n = n - (i + 1)
final_count += (i + 1) * n
最后一点:您可能会注意到,offset
现在从零开始计算到列表的长度,而 n
则相反,从列表的长度开始计算到零。你可以把它结合起来,所以你不需要两者。