算法的实施例具有不同的最坏情况下的上限，最糟糕的情况下边界和最好情况界限？ [英] Example of algorithm which has different worst case upper bound, worst case lower bound and best case bounds?

问题描述

有没有什么算法，使得用于为一组最坏情况的实例的S，A具有不同的最坏情况的上限和最坏情况下界？此外，它应该有不同的情况下，最好的边界不等于任何最坏情况界限，对一些组输入。

Is there any algorithm A, such that for a set of worst case instances S for A, A has different worst case upper bound and worst case lower bound? Moreover it should have different best case bounds not equal to any worst case bounds,for some set of inputs.

举例说，H是一个假设的算法，使得H具有上限Ο（正^ 3），最坏的情况下下界Ω（N ^ 2）和最好的情况下的运行时间Θ（n）的

For example say H is a hypothetical algorithm such that H has worst case upper bound Ο(n^3), worst case lower bound Ω(n^2) and best case running time Θ(n).

让我知道上述情况实际上是有意义的或不？

Let me know that above situation is actually meaningful or not?

感谢：）

推荐答案

下面的 ^ h 的不太自然，但也许更令人满意的定义。此函数计算输入列表的总和的立方体在一个相当愚蠢的方式

Here's a less natural but perhaps more satisfying definition of H. This function computes the cube of the sum of the input list in a rather silly manner.

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

最好情况下是结合西塔（n）的。最严格的最坏情况上限的形式为O（n ^ K）的为O（n ^ 3）。最严格的最坏情况下界的形式欧米茄（N ^ K）是欧米茄（N ^ 2）。

The best-case bound is Theta(n). The tightest worst-case upper bound of the form O(n^k) is O(n^3). The tightest worst-case lower bound of the form Omega(n^k) is Omega(n^2).

请注意，然而，在紧的绑定的任何形式上的最坏情况是西塔（F（N）），其中f（2米）=平方公尺和f（2M + 1） =立方公尺。

Note, however, that the tightest bound of any form on the worst-case is Theta(f(n)) where f(2m) = m^2 and f(2m+1) = m^3.

这篇关于算法的实施例具有不同的最坏情况下的上限，最糟糕的情况下边界和最好情况界限？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！