仅使用相等比较的唯一元素的数量
Number of unique elements only using equality comparisons
如果只能在两个元素之间进行相等比较，有没有一种方法可以比 O(n^2) 更快（最坏情况）运行 时间查找列表中唯一元素的数量？不允许对元素进行删除、复制或其他索引（循环遍历它们进行比较除外）。我们基本上不知道元素的值是什么，我们只能判断其中两个是否相同。没有关于元素分布的更多信息，你不能只假设整数。
我能做的最好的就是暴力破解 - 将当前元素与所有先前的元素进行比较，即 O(n^2) 但我不确定如何证明这是最好的 运行次。
如果一个列表包含 N 个元素且只有一个重复元素，则有 N(N-1)/2 对可能的元素可以比较是否相等，并且只有其中一对比较相等。
因此，给定任何旨在对不同元素进行计数的算法，对手可以向它提供一个包含 N 个不同元素的列表，并观察它进行了哪些比较以及它提供了什么答案。那么：
- 如果算法给出的答案不是 N，那么它就是错误的。
- 否则，如果算法进行的比较少于 N(N-1)/2 次，则至少有一对没有进行比较。对手可以将这两个元素设置为相等，并再次 运行 算法。由于它所做的所有比较都会有相同的结果，所以它会再次给出答案N，但是这次它是错误的。
因此，任何总是进行少于 N(N-1)/2 次比较的算法都必须 return 至少有一个输入的错误答案。
如果只能在两个元素之间进行相等比较，有没有一种方法可以比 O(n^2) 更快（最坏情况）运行 时间查找列表中唯一元素的数量？不允许对元素进行删除、复制或其他索引（循环遍历它们进行比较除外）。我们基本上不知道元素的值是什么，我们只能判断其中两个是否相同。没有关于元素分布的更多信息，你不能只假设整数。
我能做的最好的就是暴力破解 - 将当前元素与所有先前的元素进行比较，即 O(n^2) 但我不确定如何证明这是最好的 运行次。
如果一个列表包含 N 个元素且只有一个重复元素，则有 N(N-1)/2 对可能的元素可以比较是否相等，并且只有其中一对比较相等。
因此，给定任何旨在对不同元素进行计数的算法，对手可以向它提供一个包含 N 个不同元素的列表，并观察它进行了哪些比较以及它提供了什么答案。那么：
- 如果算法给出的答案不是 N，那么它就是错误的。
- 否则，如果算法进行的比较少于 N(N-1)/2 次，则至少有一对没有进行比较。对手可以将这两个元素设置为相等，并再次 运行 算法。由于它所做的所有比较都会有相同的结果，所以它会再次给出答案N，但是这次它是错误的。
因此，任何总是进行少于 N(N-1)/2 次比较的算法都必须 return 至少有一个输入的错误答案。