首先，我知道
和我同意的下限应该是O（nlogn）。
我不太明白的是：
有关某些特殊情况下，比较的＃实际上可能比下限还低。例如，使用的冒泡排序的排序一个已经排序的数组。比较的＃为O（n）。
因此，如何真正理解的想法的下限的？
在Wikipedial的经典定义： en.wikipedia/wiki/Upper_and_lower_bounds没有太大的帮助。
我目前对此的理解是：
下限基于比较的排序实际上是上限为最坏的情况。
即，如何最好你可以在最坏的情况下
这是正确的？谢谢你。
解决方案下限的比较为基础的分选实际上是上限最好的情况
无。这是你包围的功能是在最坏情况运行最好的排序算法的时间。
想象一下以下游戏：
在为O（n log n）的上限意味着你可以限制你的成本最多为O（n log n）的美元，不管我选择什么样的输入序列。
的Ω（N log n）的，我可以强迫你支付至少Ω（N log n）的美元，不管你选择什么样的排序算法。下界手段
另外：下界是O（n log n）的没有任何意义。 O（F（N））指至多一个常数乘以F（N）。但下限是指至少...。所以说下界为O（n log n）的酷似说：你可以保存至 50％或更多！ - 这是完全没有意义！正确的符号为下界是Ω（...）。
First, I know
And I agree the lower bound should be O(nlogn).
What I don't quite understand is:
For some special cases, the # of comparisons could actually be even lower than the lower bound. For example, use bubble sort to sort an already sorted array. The # of comparisons is O(n).
So how to actually understand the idea of lower bound?
The classical definition on Wikipedial: en.wikipedia/wiki/Upper_and_lower_bounds does not help much.
My current understanding of this is:
lower bound of the comparison-based sorting is actually the upper bound for the worst case.
namely, how best you could in the worst case.
Is this correct? Thanks.
解决方案lower bound of the comparison-based sorting is actually the upper bound for the best case.
No.
The function that you are bounding is the worst-case running time of the best possible sorting algorithm.
Imagine the following game:
The O(n log n) upper bound means you can limit your cost to at most O(n log n) dollars, no matter what input sequence I choose.
The Ω(n log n) lower bound means that I can force you to pay at least Ω(n log n) dollars, no matter what sorting algorithm you choose.
Also: "The lower bound is O(n log n)" doesn't make any sense. O(f(n)) means "at most a constant times f(n)". But "lower bound" means "at least ...". So saying "a lower bound of O(n log n)" is exactly like saying "You can save up to 50% or more!" — it's completely meaningless! The correct notation for lower bounds is Ω(...).