当元素出现超过 n / 2 次时，是否可以在 O(n) 中对数组进行排序？
Will it work to sort an array in O(n) when an element occurs more than n / 2 times?
假设数组中元素的比较时间为O(n)，如果一个元素出现超过n / 2次，是否可以在O(n)中对数组进行排序？
其实应该是可以的，因为有这个中值算法可以找到一个数组的中间值，还是我错了？
没有
假设数组中最小的元素出现超过 n / 2 次，比方说 ceil(n / 2) + 1。那么还有n - (ceil(n / 2) + 1) ~ n / 2 = O(n)个元素需要排序，还需要O(n log n)个时间。
没有
即使一个元素出现超过n/999次，复杂度也不会O(n)，因为对剩余元素进行排序仍然是O(n log n)。
复杂度并没有告诉你你的算法需要多少时间来完成，它表明当你改变时这个时间会改变多少n，即使这个改变的因素很小.
然而，一些分布可以影响复杂性，例如，如果你知道只允许m值（那么aO(n) 算法在于使用寄存器来计算每个允许值的出现次数）。
假设数组中元素的比较时间为O(n)，如果一个元素出现超过n / 2次，是否可以在O(n)中对数组进行排序？
其实应该是可以的，因为有这个中值算法可以找到一个数组的中间值，还是我错了？
没有
假设数组中最小的元素出现超过 n / 2 次，比方说 ceil(n / 2) + 1。那么还有n - (ceil(n / 2) + 1) ~ n / 2 = O(n)个元素需要排序，还需要O(n log n)个时间。
没有
即使一个元素出现超过n/999次，复杂度也不会O(n)，因为对剩余元素进行排序仍然是O(n log n)。
复杂度并没有告诉你你的算法需要多少时间来完成，它表明当你改变时这个时间会改变多少n，即使这个改变的因素很小.
然而，一些分布可以影响复杂性，例如，如果你知道只允许m值（那么aO(n) 算法在于使用寄存器来计算每个允许值的出现次数）。