Python list.pop(i) 时间复杂度？

Question

我上网查了一下才知道list.pop()时间复杂度为 O(1) 但 list.pop(i)有 O(n) 的时间复杂度。我在写 leetcode 的时候，很多人都在用 pop(i)在 for 循环中，他们说它是 O(n) 时间复杂度，实际上它比我的代码快，我的代码只使用一个循环，但在该循环中使用多行。我想知道为什么会发生这种情况，我应该使用 pop(i)而不是很多行来避免它？

示例:Leetcode 26. 从排序数组中删除重复项

我的代码:(比 75% 快)

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, 0
        count = 1
        while right < len(nums)-1:
            if nums[right] == nums[right+1]:
                right += 1
            else:
                nums[left+1]=nums[right+1]
                left += 1
                right += 1
                count += 1
        return count

和其他人的代码，比 90% 快:(这家伙不说 O(n)，但为什么 O(n^2) 比我的 O(n) 快？)

https://leetcode.com/problems/remove-duplicates-from-sorted-array/discuss/477370/python-3%3A-straight-forward-6-lines-solution-90-faster-100-less-memory

我的优化代码(快于 89%)

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, 0
        while right < len(nums)-1:
            if nums[right] != nums[right+1]:
                nums[left+1]=nums[right+1]
                left += 1
            right += 1
        return left + 1

Answer 1

您的算法确实需要 O(n) 时间，而“逆序弹出”算法确实需要 O(n²) 时间。然而，LeetCode 并未报告您的时间复杂度优于 89% 的提交；它报告您的实际运行时间优于所有提交的 89%。实际运行时间取决于测试算法的输入；不仅是大小，还有重复的数量。

它还取决于如何平均跨多个测试用例的运行时间；如果大多数测试用例是针对二次解更快的小输入，那么即使二次解的时间复杂度更高，它也可能整体领先。 @Heap Overflow 在评论中还指出，LeetCode 判断系统的开销时间与算法运行所需的时间相比成比例地大且变化很大，因此差异可能仅仅是由于该开销的随机变化造成的。

为了阐明这一点，我使用 timeit 测量了运行时间。 .下图显示了我的结果；考虑到时间复杂性，这些形状正是您所期望的，并且交叉点介于 8000 < n < 9000 之间。在我的机器上。这是基于排序列表，其中每个不同的元素平均出现两次。我用来生成时间的代码如下。



计时码:

def linear_solution(nums):
    left, right = 0, 0
    while right < len(nums)-1:
        if nums[right] != nums[right+1]:
            nums[left+1]=nums[right+1]
            left += 1
        right += 1
    return left + 1

def quadratic_solution(nums):
    prev_obj = []
    for i in range(len(nums)-1,-1,-1):
        if prev_obj == nums[i]:
            nums.pop(i)
        prev_obj = nums[i]
    return len(nums)

from random import randint
from timeit import timeit

def gen_list(n):
    max_n = n // 2
    return sorted(randint(0, max_n) for i in range(n))

# I used a step size of 1000 up to 15000, then a step size of 5000 up to 50000
step = 1000
max_n = 15000
reps = 100

print('n', 'linear time (ms)', 'quadratic time (ms)', sep='\t')
for n in range(step, max_n+1, step):
    # generate input lists
    lsts1 = [ gen_list(n) for i in range(reps) ]
    # copy the lists by value, since the algorithms will mutate them
    lsts2 = [ list(g) for g in lsts1 ]
    # use iterators to supply the input lists one-by-one to timeit
    iter1 = iter(lsts1)
    iter2 = iter(lsts2)
    t1 = timeit(lambda: linear_solution(next(iter1)), number=reps)
    t2 = timeit(lambda: quadratic_solution(next(iter2)), number=reps)
    # timeit reports the total time in seconds across all reps
    print(n, 1000*t1/reps, 1000*t2/reps, sep='\t')

结论是，对于足够大的输入，您的算法确实比二次解法更快，但是 LeetCode 用来测量运行时间的输入“不够大”，无法克服判断开销的变化，而且平均值包括在二次算法更快的较小输入上测量的时间。