问题的下界

如何度量一个问题的困难度?
如果问题可以由一个具有较低时间复杂度的算法解决,那么该问题是简单问题;否则,该问题是困难的问题。
defineoflowerbound

一般情况下,都用最坏情况来描述下界。

我们必须明白每个更高下界的找出都是通过理论分析得到的,而不是纯粹的猜想。

应注意到,定义的下界不是唯一的。比如说,排序问题的下界是 nlogn,在证明出nlogn之前,可能认为 n 是排序算法的下界,甚至认为1是排序算法的下界(因为最好情况下可以只需要1步完成算法),对于nlogn,n,1 这三个下界都是正确的,但是只有nlogn是有意义的。
下界太低就不具有意义,所以希望下界尽可能的高。
排序算法的下界是nlogn,因为堆排序在最坏的情况下,它的时间复杂度是O(nlogn)

 

如何知道一个算法是最优的?
如果一个算法的时间复杂度等于这个问题的下界,那么该算法是最优的。因此,下界和算法都不能够再进一步提高了。

lowerboundofkeysummary

 

平均情况下,快排是最优的算法;

最坏情况下,堆排序是最优的排序算法;

排序问题的下界是Ω(nlogn)

 

 

Tagged on:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>