我正在尝试证明这个问题：
如果存在可以确定n个元素的排序列表中是否有重复元素的算法，则所需比较数的下限为n-1。
n-1
我对上下限不太熟悉，我似乎对此感到困惑，有人可以帮我提供一个易于理解的证明吗？
问题陈述并不严格。应该说“ 最坏情况下 的比较次数”。
在排序数组中，n-1成对的连续元素之间存在关系，它们是<或=。如果所有元素都不相同，则无法从其他比较中推断出比较结果。因此，您无法避免进行详尽的搜索并进行n-1测试。
<
=
顺便说一句，n-1在最坏的情况下也是一个上限，因为在详尽搜索之后，您总会得到答案。
最好的情况是，当前两个元素相等时，可以在完全1比较后找到答案。因此，最佳情况的下限和上限均为1。
1
