Python - del my_list [ :]? 的大 O

Question

del my_list[:]的大O是什么？这个命令删除列表中的所有元素。我的理解是它将是 O(n)。 n 是列表的长度。

因此这段代码的大 O 应该是 bigO(n^2)，对吗？

请注意，这不是为了学校，而是为了我在面试练习时的理解。

from copy import deepcopy
class Solution:
    # @param A : list of integers
    # @return an integer
    def removeDuplicates(self, A):
        copy_array = deepcopy(A)
        del A[:]

        for j in copy_array:
            if j in A:
                pass
            else:
                A.append(j)

        return len(A)

Answer 1

del 在这里不影响 big-O，循环是 n 和 A 测试中的 j 是 n，所以嵌套循环是O(n**2)； del 是 O(n)，但它不是循环的一部分，并且由于它是低阶工作，因此被忽略。

旁注:O(n) 的解决方案是使用 collections.OrderedDict去重，保留顺序，使方法的主体只是:

A[:] = collections.OrderedDict.fromkeys(A)
return len(A)