时间戳

首页 > 解决方案 > Python list.pop(i) 时间复杂度？

python - 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

我的优化代码（快于 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

标签： pythonalgorithmtime-complexity

解决方案

您的算法确实需要 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 用来测量运行时间的输入“不够大”，无法克服判断开销的变化，而且平均值包括在二次算法更快的较小输入上测量的时间。

推荐阅读