设A是含有n个元素的数组 如果元素x在A出现的次数大于n/2 则称x是A的主元素。 （1）如果A中元素是可
已帮助 人
设A是含有n个元素的数组，如果元素x在A出现的次数大于n/2，则称x是A的主元素。 （1）如果A中元素是可以排序的，设计一个O（nlogn)时间的算法，判断A中是否存在主元素。 （2）对于（1）中可排序的数组，能否设计一个O（n)时间的算法？ （3）如果A中元素只能进行“是否相等”的测试，但是不能进行排序，设计一个算法判断A中是否存在主元素。
回答
共1条回复-
证明 (1)因为|A|=n，所以|ρ(A)|=2 n ． 所以A上有2 n 个一元关系． (2)因为|A|=n，所以|A×A|=n 2 ，所以有|ρ(A×A)|=2 n 2 ，因此A上有2 n 2 个二元关系．