关于复杂性（如果使用基于比较的排序算法） [英] Regarding complexity (if comparison based sorting algorithm used)

问题描述

大家都知道，基于比较模型中的任何排序算法下界nlogn即欧米茄（nlogn）的。 这可以用数学证明。

as we all know that any sorting algorithm based on comparison model has lower bound of nlogn i.e Omega(nlogn). which can be proved mathematically.

但我们都知道荷兰国旗问题可以排序为O 3个不同的元素（重复使用）（n）的time.It也是基于比较模型，但可以在O（n）的时间进行排序。 那么如何才能证明下界基于比较模型排序，因为荷兰国旗问题有点违反了。

but as we all know dutch flag problem can sort 3 distinct elements (used repeatedly) in O(n) time.It is also based on comparison model but can sort in O(n) time. so how can we justify lower bound of sorting based on comparison model , because dutch flag problem kinda violates that.

请帮我理解的差异......

please help me understanding the difference.....

感谢

推荐答案

在我看来，这不是下界相关的矛盾，因为它是一个特定的情况下（值的可能范围比小元素的总数量，实际上它是一个常数，3），它可以被利用来找到一个算法快于O（N * LOGN）这是下界一般基于比较的排序算法（例如，你有没有关于该序列的内容的信息）。

In my opinion, this is not a relevant "contradiction" of the lower bound, because it is a particular case (the possible range of values is smaller than the total number of elements, in fact it is a constant, 3) which can be exploited to find an algorithm faster than O(N*logN), which is the lower bound for a general comparison-based sorting algorithm (i.e. where you have no information about the content of the sequence).

一般在N个元素的范围是0..K用K＆所述的情况下N，你就可以有效地利用非比较有点像计数排序，以解决问题为O（N）。

Generally in the case where N elements are in the range 0..K with K < N you can efficiently exploit a non-comparison sort like counting sort to solve the problem in O(N).

这篇关于关于复杂性（如果使用基于比较的排序算法）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！