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

我上网查了一下才知道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 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

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

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

为了阐明这一点，我使用以下方法测量了运行时间timeit https://docs.python.org/3/library/timeit.html。下图显示了我的结果；考虑到时间复杂度，这些形状正是您所期望的，并且交叉点介于两者之间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 用于测量运行时间的输入“不够大”，不足以克服判断开销的变化，并且平均值包括在较小的输入上测量的时间，其中二次算法更快。