这在很大程度上取决于‘比较’一词的含义。
如果比较相等性，则@Sven-Marnach 的答案适用：长度相同时为 O（n），长度不同时为 O（1）。
如果您要将多个列表相互比较，则使用哈希函数会有所帮助：对于不同的列表（具有不同的哈希值），其复杂度为 O(1)，而对于具有相同哈希值的列表，其复杂度可能仍为 O(n)，因为哈希值可能会发生冲突，您必须进行真正的比较。这可以通过使用多个哈希函数来缓解，因此发生冲突的概率会大大降低。
请注意，计算长度为 n 的列表的哈希值仍然需要 O（n），因此这里没有免费午餐。
如果您想比较两个列表的相似性，您可能需要 Levenshtein 距离 ，在简单的情况下，该距离是时间的二次方，但可以通过惰性求值变为线性，但可能会花费大量的内存。
创建一个列表所需要做的完整更改列表 diff ，则在 Wikipedia 中提到的最佳实现中它是二次的。
