这段代码的大 O 表示法是什么？

Question

它会是 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

Answer 1

在我看来，如果没有 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 表示法是什么？

What will be the big-O notation for this code?

python

algorithm

time-complexity