设计和分析线性时间算法

Question

设计和分析线性时间算法以确定在n个元素的列表中是否存在元素,其在列表中至少重复n/10次.

我怎样才能做到这一点？我发布了自己的想法作为答案.

Answer 1

我认为这些元素具有可比性.

执行以下选择算法:n/10th,2n/10th,...,9n/10th,10(n/10)个最小元素¹

这些是你的候选人.检查每个#occurrences,如果其中一个重复至少n/10次答案true.否则就是false.

证明:
如果一个元素出现至少n/10次,那么它必须与k*n/10某些元素"相交" k(在排序列表中)².因此,这个元素将被选为"候选者",稍后您将发现(通过计数)它出现的次数,并将返回true.

如果没有重复的元素n/10次数,算法将false在检查每个候选者的最后一步中返回.

复杂性:
每个选择算法都是O(n),并且完成了10次.此外每名候选人要求列表,这也是对线性扫描O(n)总额在O(n)整体,但可怕的常量.

解释:

(1)选择算法会在排序列表中找到索引为n/10,2n/10,... 9n/10的元素,算法本身只是 O(n)

(2)让我们看一下[1,2,..,100,100,..,100](11次100)的例子.
请注意,列表已排序,元素100显示在:( list[9*n/10]索引9*n/10)中.选择算法的想法是 - 即使你随机播放列表 - select(list,9*n/10)将始终返回相同的元素 - 在这种情况下为100 - 因为它是9n/10排序列表中的第th个元素(这是算法所做的).

现在,您可以看到,对于e重复n/10次数的每个元素(让它),有一些索引i,使得在列表的排序版本中,索引中的所有元素都i,i+1,...,i+n/10将是e.其中一个指数必须是k*n/10某些指数k(说服自己为什么!).因此,选择算法k*n/10将产生e.