下界理解为基于比较的排序算法 [英] understanding of lower bound for comparison-based sorting algorithm

问题描述

首先，我知道

1. 在下界是O（nlogn）
2. ，以及如何证明它

和我同意的下限应该是O（nlogn）。

我不太明白的是：

有关某些特殊情况下，比较的＃实际上可能比下限还低。例如，使用的冒泡排序的排序一个已经排序的数组。比较的＃为O（n）。

因此，如何真正理解的想法的下限的？

在Wikipedial的经典定义： http://en.wikipedia.org/wiki/Upper_and_lower_bounds没有太大的帮助。

我目前对此的理解是：

下限基于比较的排序实际上是上限为最坏的情况。

即，如何最好你可以在最坏的情况下

这是正确的？谢谢你。

解决方案

  

下限的比较为基础的分选实际上是上限最好的情况

无。

这是你包围的功能是在最坏情况运行最好的排序算法的时间。

想象一下以下游戏：

1. 我们选择一些数n。
2. 您挑自己喜欢的排序算法。
3. 在看着你的算法，我挑长度为n的一些输入序列。
4. 我们在我的投入运行你的算法，你给我一块钱每一个执行的指令。

在为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

1. lower bound is O(nlogn)
2. and how to prove it

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: http://en.wikipedia.org/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:

1. We choose some number n.
2. You pick your favorite sorting algorithm.
3. After looking at your algorithm, I pick some input sequence of length n.
4. We run your algorithm on my input, and you give me a dollar for every executed instruction.

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 Ω(...).

这篇关于下界理解为基于比较的排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！