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