3.5 非基于比较的算法

下面考虑是否可能以少于O(nlogn)的消息数来选出领导者。这个问题的答案是否定的，正如我们将会简短证明一个不可能性结果——Ω(nlogn)的下界。但是这个结论只适用于那些使用比较操作来处理UID的算法（基于比较的算法在3.6节中定义）。

在本节中，我们允许UID为正整数，且允许对它们进行一般的数学运算。在这种情况下，我们给出两个算法，时间片（TimeSlice）算法和变速（VariableSpeeds）算法，它们都是消息数为O(n)的算法。这两个算法的存在说明了在一般情况下，下限低于Ω(nlogn)是可能的。