关于插入排序矛盾Cormen [英] Contradiction in Cormen regarding Insertion sort
问题描述
在Cormen定理3.1说
例如，在最好的情况下运行插入排序是大欧米茄（N），而最坏情况下的时间运行插入排序时间大哦（N ^ 2）。 插入的运行时间之间的排序因此属于大欧米茄（N）和 Bigoh（N ^ 2）
现在，如果我们看一下练习3.1-6它要求
证明了算法的运行时间是大-θ（G（N））当且仅当它的最坏的情况下运行时间大哦（G （N））和最好的情况下运行时间大欧米茄（G（N））
- 我是唯一一个谁看到一对矛盾在这里。
- 我的意思是，如果我们遵守了已被证明的问题，我们的结论是渐近更严密的界限（ F（N）=大-θ（G（N））），我们需要有 F（N）=大欧米茄（G（N））作为算法的最好的情况下和大哦（G（N））在最坏的情况下
- 但是，在案件的插入排序的最好的情况下时间复杂度为大欧米茄（N）和最坏的情况下时间复杂度为大哦（N ^ 2）
我觉得你是一个有点困惑here.Let我澄清几点你。
运行时间可能意味着两件事：该程序，或像有界函数的实际运行时间THETA或大哦（所以它有助于把这种时间复杂度，以避免混乱）.Hereafter我们将使用运行时间程序的实际运行时间，和时间复杂度来表示大哦/ THETA符号。
要拿起大哦看我的答案<一href="http://stackoverflow.com/questions/17275612/complexitys-and-run-times/17301468#17301468">here.
一旦你明确与大哦，其他功能下降到位easily.When我们说T（n）是欧米茄（G（N）），是指在一定点右边k为曲线CG（N ）的境界，从below.OR的运行时间曲线换句话说：
T（N）＆GT; = CG（N）对所有的n＆GT; = K，而对于一些常数c独立的输入大小。
和θ符号就像是说：我只是一个功能，但使用不同的常数，你可以让我绑定的运行时间曲线，从上面和下面
所以，当我们说T（n）是THETA（G（N）），我们指的是
c1.g（N）==氏/ P>
现在我们知道什么功能的意思是，让我们看到CLRS在混乱中得到的。
例如，运行插入排序的时间最好的情况是大欧米茄（N），运行插入时间排序是大哦（N ^ 2），而最坏的情况。插入的运行时间大欧米茄（n）和Bigoh（N ^ 2）
之间的排序因此属于
运行时间CLRS这里指的实际运行时间T（n）的。它的措辞不好，这不是你的错，你misunderstood.In事实上，我会继续前进，说他们它的话不对什么样的在，一个功能无论是在集合O（G（N）），或者它不是属于研究。所以这是一个错误。
证明了算法的运行时间是大-θ（G（N）），当且仅当其最坏情况下的运行时间是大哦（G（N））和运行时间的最好的情况是大欧米茄（G（ N））
下面CLRS意味着运行时间函数T（n）和他们希望你搞清楚的时间复杂度。
In Cormen theorem 3.1 says that
For example, the best case running time of insertion sort is big-omega(n), whereas worst case running time of Insertion sort is Big-oh(n^2). The running time of insertion sort therefore falls between big-omega(n) and Bigoh(n^2)
Now if we look at the Exercise 3.1-6 it asks
Prove that the running time of an algorithm is Big-theta(g(n)) iff its worst case running time is Big-oh(g(n)) and its best case running time is big-omega(g(n))
- Am I the only one who sees a contradiction here.
- I mean if we abide by the question that has to be proved, we conclude that for asymptotically tighter bounds (f(n) = Big-theta(g(n))) we need to have f(n) = big-omega(g(n)) for the algorithm's best case and Big-oh(g(n)) in its worst case
- But in case of Insertion sort best case time complexity is big-omega(n) and worst case time complexity is Big-oh(n^2)
I think you are a bit confused here.Let me clarify a few points for you.
Running time can mean two things: the actual running time of the program, or the bounded function like theta or big-oh(so it helps to call this time complexity, in order to avoid the confusion).Hereafter we will use running time for program's actual running time, and time complexity to denote the Big-Oh/theta notation.
To pick up Big-Oh read my answer here.
Once you are clear with Big-Oh, the other functions fall in place easily.When we say T(n) is Omega(g(n)), we mean to the right of some point k the curve c.g(n) bounds the running time curve from below.OR in other words:
T(n)>=c.g(n) for all n>=k, and for some constant c independent of input size.
And theta notation is like saying "I am just one function, but using different constants you can make me bound the running time curve from above and from below"
So when we say T(n) is theta(g(n)), we mean
c1.g(n)==k
Now we know what the functions mean, let's see where CLRS got in the confusion.
For example, the best case running time of insertion sort is big-omega(n), whereas worst case running time of Insertion sort is Big-oh(n^2). The running time of insertion sort therefore falls between big-omega(n) and Bigoh(n^2)
Here by running time CLRS means the actual running time T(n).It's poorly worded, and it's not your fault that you misunderstood.In fact I would go ahead and say they it's wrong.There is nothing like falls in between, a function is either in the set O(g(n)) or it isn't. So it's an error.
Prove that the running time of an algorithm is Big-theta(g(n)) iff its worst case running time is Big-oh(g(n)) and its best case running time is big-omega(g(n))
Here CLRS means the running time function T(n) and they want you to figure out the time complexity.
这篇关于关于插入排序矛盾Cormen的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
