证明算法具有下界 [英] Prove that an algorithm has a lower bound

问题描述

我正在尝试证明这个问题：

I'm trying to prove this problem:

如果存在一种算法可以确定n $ b $的排序列表b元素中有重复的元素，而所需的比较次数
的下界为 n-1 。

我对上下限不太熟悉，我似乎感到困惑，有人可以帮我提供一个易于理解的证明吗？

I'm not quite familiar with lower and higher bounds and I seem to confuse it, can someone help me with an easy to understand proof?

推荐答案

问题陈述并不严格。它应该说最坏情况下的比较次数 。

The problem statement is not rigorous. It should say "the number of comparisons in the worst case".

在排序数组中，有 n一对连续元素之间的关系-1 是< 或 = 。如果所有元素都不相同，则无法从其他比较中推断出比较结果。因此，您无法避免进行详尽的搜索，最多进行 n-1 个测试。

In a sorted array, there are n-1 relations between pairs of successive elements, which are either < or =. If all elements are different, you cannot deduce the outcome of a comparison from that of other comparisons. Hence you cannot avoid an exhaustive search, taking up to n-1 tests.

顺便说一句， n-1 也是最坏情况的上限，因为在详尽搜索之后，您总能得到答案。

By the way, n-1 is also an upper bound on the worst case, as after the exhaustive search you always have the answer.

在最佳情况下，当前两个元素相等时，您会在恰好 1之后找到答案比较。因此，最佳情况的下限和上限均为 1 。

In the best case, when the first two elements are equal, you find the answer after exactly 1 comparison. Hence, lower and upper bounds on the best case are both 1.

这篇关于证明算法具有下界的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！