algorithm - 具有不同最坏情况上限、最坏情况下限和最佳情况下限的算法示例？

Question

是否存在任何算法 A，使得对于 A 的一组最坏情况实例 S，A 具有不同的最坏情况上限和最坏情况下限？此外，对于某些输入集，它应该具有不等于任何最坏情况界限的不同最佳情况界限。

例如，假设 H 是一种假设算法，H 具有最坏情况上限 Ω(n^3)、最坏情况下限 Ω(n^2) 和最佳情况运行时间 Θ(n)。

请问上面的情况到底有没有意义？

谢谢:)

Answer 1

按照您描述的方式，选择任何二次排序算法，比如冒泡排序:

• 最坏情况上限可以说是O(n^3)。

• 最坏情况下限可以说是Ω(n^2)。

• 当输入已经排序时，最好的运行时间可以说是Θ(n)然后在开始算法之前通过单次检查，或者使用在这种情况下过早终止算法的优化。