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

Question

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

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

让我知道上述情况实际上是否有意义？

谢谢 ：）

Answer 1

你描述它的方式，选择任何二次排序算法，比如冒泡排序：

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

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

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

Answer 2

这是一个不太自然但也许更令人满意的定义H。此函数以一种相当愚蠢的方式计算输入列表之和的立方。

def H(lst):
    s1 = 0
    for x in lst:
        s1 += x
    if s1 == 0:
        return 0
    elif len(lst) % 2 == 0:
        s2 = 0
        for x in lst:
            for y in lst:
                s2 += x * y
        return s1 * s2
    else:
        s3 = 0
        for x in lst:
            for y in lst:
                for z in lst:
                    s3 += x * y * z
        return s3

最佳情况界限是 Theta(n)。O(n^k) 形式的最严格的最坏情况上限是 O(n^3)。Ω(n^k) 形式的最严格的最坏情况下限是 Ω(n^2)。

但是请注意，在最坏情况下，任何形式的最严格界限是 Θ(f(n))，其中 f(2m) = m^2 和 f(2m+1) = m^3。