这段代码的大 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 则相反,从列表的长度开始计算到零。你可以把它结合起来,所以你不需要两者。