假设列表仅包含可散列对象。
顺便说一句，我不确定这个问题是否有意义，因为在涉及复杂性和学术问题时，我是一个完全的菜鸟。
问问题
3144 次
2 回答
20
如果两个列表的长度为 n，比较两个列表的复杂度为 O(n)，如果两个列表的长度不同，则为 O(1)。
于 2012-07-03T15:15:44.893 回答
5
这在很大程度上取决于“比较”一词的含义。
如果您比较相等性，@Sven-Marnach 的答案适用：相同长度为 O(n)，不同长度为 O(1)。
如果您将许多列表相互比较，则使用哈希函数可以帮助您：对于不同的列表（具有不同的哈希）它是 O(1)，对于具有相同哈希的列表可能仍然是 O(n)，因为哈希值可能冲突，你必须做一个真正的比较。这可以通过使用多个哈希函数来缓解，因此冲突的概率大大降低。
请注意，仍然需要 O(n) 来计算长度为 n 的列表的哈希值，所以这里没有免费的午餐。
如果您想比较两个列表的相似性，您可能需要Levenshtein 距离，它在简单的情况下是时间的二次方，但可以通过惰性求值使其成为线性距离，这可能会耗费大量内存。
如果您想计算完整的更改列表以从另一个列表中生成一个列表 ( diff)，它在 Wikipedia 中提到的最佳实现中是二次的。
于 2012-07-03T15:33:51.403 回答