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\xc2\xb2) 时间。然而，LeetCode 并没有报告说你的时间复杂度优于 89% 的提交；据报告，您的实际运行时间优于所有提交的 89%。实际运行时间取决于测试算法的输入；不仅是大小，还有重复的数量。

\n\n

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

\n\n

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

\n\n

\n\n

计时代码：

\n\n

def linear_solution(nums):\n    left, right = 0, 0\n    while right < len(nums)-1:\n        if nums[right] != nums[right+1]:\n            nums[left+1]=nums[right+1]\n            left += 1\n        right += 1\n    return left + 1\n\ndef quadratic_solution(nums):\n    prev_obj = []\n    for i in range(len(nums)-1,-1,-1):\n        if prev_obj == nums[i]:\n            nums.pop(i)\n        prev_obj = nums[i]\n    return len(nums)\n\nfrom random import randint\nfrom timeit import timeit\n\ndef gen_list(n):\n    max_n = n // 2\n    return sorted(randint(0, max_n) for i in range(n))\n\n# I used a step size of 1000 up to 15000, then a step size of 5000 up to 50000\nstep = 1000\nmax_n = 15000\nreps = 100\n\nprint(\'n\', \'linear time (ms)\', \'quadratic time (ms)\', sep=\'\\t\')\nfor n in range(step, max_n+1, step):\n    # generate input lists\n    lsts1 = [ gen_list(n) for i in range(reps) ]\n    # copy the lists by value, since the algorithms will mutate them\n    lsts2 = [ list(g) for g in lsts1 ]\n    # use iterators to supply the input lists one-by-one to timeit\n    iter1 = iter(lsts1)\n    iter2 = iter(lsts2)\n    t1 = timeit(lambda: linear_solution(next(iter1)), number=reps)\n    t2 = timeit(lambda: quadratic_solution(next(iter2)), number=reps)\n    # timeit reports the total time in seconds across all reps\n    print(n, 1000*t1/reps, 1000*t2/reps, sep=\'\\t\')\n

\n\n

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

\n