2

Hyperspec 中的以下声明是这样的，这是否有逻辑上的原因？“如果 list-1 和 list-2 之间存在重复，则结果中只会出现一个重复的实例。如果 list-1 或 list-2 中有重复条目，则冗余条目可能会出现，也可能不会出现结果。”

在我读到这篇文章之前，我一直假设 union 应该返回一个唯一的列表，并且对我的代码没有这样做的原因感到沮丧。删除列表之间但不在列表中的重复项似乎也很奇怪。为什么还要指定这个？

似乎人们应该能够假设 union 将产生集合元素的唯一列表，或者我错过了什么？

有关 Hyperspec 的完整页面，请参见http://clhs.lisp.se/Body/f_unionc.htm

4

2 回答 2

5

如果您的代码仅包含具有唯一元素（如1 2 3）的集合，UNION则将保留此属性。

如果您的代码具有包含非唯一元素（如1 2 2 3）的集合，则UNION无需努力在结果集中强制执行唯一性。

删除重复项是通过一个单独的函数完成的：REMOVE-DUPLICATES.

于 2012-05-30T19:25:10.670 回答
4

假设作为 UNION 参数的两个列表的元素都是唯一的，则意味着算法在最坏情况下（不可排序、不可散列的元素）的复杂度为 O(n*m)。另一方面，在这种情况下删除列表中的重复项是 O(n^2)。即使在没有重复项的情况下，使 UNION 删除重复项也会使运行时间大约增加三倍，因为大部分时间都花在了比较上。

于 2012-05-30T15:48:01.637 回答