此算法的效率可以线性吗？

Question

我的教科书说以下算法的效率为O（n）：

list = [5,8,4,5]

def check_for_duplicates(list):
    dups = []
    for i in range(len(list)):
        if list[i] not in dups:
            dups.append(list[i])
        else:
            return True

    return False

但是为什么呢？我问是因为in运算的效率也为O（n）（根据this resource）。如果以list为例，程序需要在列表上迭代4次。但是每次迭代，dups都会保持更快的增长。因此，对于list上的第一次迭代，dups没有任何元素，但是对于第二次迭代，它具有一个元素，对于第三两个元素和对于第四三个元素。这样会不会在in迭代的基础上为list操作进行1 + 2 + 3 = 6额外的迭代？但是，如果这是真的，那么这会不会显着改变效率，因为额外迭代的总和每次迭代都会更快地增长？

Answer 1

由于您所指出的原因，您正确地在此处发布的代码的运行时是O（n ²），而不是O（n）。

概念上，您正在实现的算法如下：

• 维护到目前为止看到的所有项目的集合。
• 对于列表中的每个项目：
  • 如果该项目在集合中，则报告存在重复项。
  • 否则，将其添加到集合中。
• 报告没有重复。

您在此处发布的代码之所以缓慢，是因为使用列表跟踪到目前为止看到的项目时，检查重复项是否存在的成本为O（n）。实际上，如果您使用的是现有元素列表，那么您所做的本质上等同于仅检查数组的先前元素以查看它们是否相等！

您可以通过切换实现方式来加快速度，以便您使用set来跟踪先前的元素而不是列表。集具有（预期的）O（1）查找和插入，因此这将使您的代码在（预期的）O（1）时间中运行。