证明算法有下界
Prove that an algorithm has a lower bound
我正在尝试证明这个问题：
if an algorithm exists that can determine if a sorted list of n
elements has duplicate elements in it, than the number of comparisons
needed has a lower bound of n-1.
我对下界和上界不是很熟悉，我好像把它弄混了，谁能帮我举个通俗易懂的证明？
如果你有数组list = {1, 2, 3, 4, 5}，你必须比较1和2、2和3、3和4等等，以确定它是否有重复项.
所以总比较次数为4，元素总数为5，因此需要n-1次比较。
问题表述不严谨。它应该说 "the number of comparisons in the worst case".
在排序数组中，连续元素对之间存在 n-1 关系，即 < 或 =。如果所有元素都不同，则无法从其他比较的结果中推断出比较的结果。因此，您无法避免进行详尽搜索，最多进行 n-1 次测试。
顺便说一下，n-1 也是最坏情况的上限，因为在穷举搜索之后你总能找到答案。
在最好的情况下，当前两个元素相等时，恰好1 比较后找到答案。因此，最佳情况下的下限和上限都是 1.
我正在尝试证明这个问题：
if an algorithm exists that can determine if a sorted list of n elements has duplicate elements in it, than the number of comparisons needed has a lower bound of
n-1.
我对下界和上界不是很熟悉，我好像把它弄混了，谁能帮我举个通俗易懂的证明？
如果你有数组list = {1, 2, 3, 4, 5}，你必须比较1和2、2和3、3和4等等，以确定它是否有重复项.
所以总比较次数为4，元素总数为5，因此需要n-1次比较。
问题表述不严谨。它应该说 "the number of comparisons in the worst case".
在排序数组中，连续元素对之间存在 n-1 关系，即 < 或 =。如果所有元素都不同，则无法从其他比较的结果中推断出比较的结果。因此，您无法避免进行详尽搜索，最多进行 n-1 次测试。
顺便说一下，n-1 也是最坏情况的上限，因为在穷举搜索之后你总能找到答案。
在最好的情况下，当前两个元素相等时，恰好1 比较后找到答案。因此，最佳情况下的下限和上限都是 1.