代码之家  ›  专栏  ›  技术社区  ›  Xinus

o、_)和_之间的区别是什么?

  •  29
  • Xinus  · 技术社区  · 15 年前

    我在学习算法分析。我很难理解O、_)和_之间的区别。

    定义方法如下:

    • f(n) = O(g(n)) 方法 c · g(n) 是一个 上界 f(n) .因此存在 一些常数 c 这样 F(N) 是 永远是 C·G(n) ,足够大 n (即, n ≥ n0 对于某个常数 n0 )
    • f(n) = Ω(g(n)) 方法 C·G(n) 是一个 下界 f(n) . 因此存在 一些常数 C 这样 f(n) 是 永远永远 C·G(n) 为了所有 n~(y)ωn0 .
    • f(n) = Θ(g(n)) 方法 c1 · g(n) 是上的上界 f(n) c2 · g(n) 是一个 下界 f(n) ,全部 n~(y)ωn0 . 因此存在常数 c1 c2 这样 f(n) ≤ c1 ·g(n) f(n) ≥ c2 ·g(n) . 这意味着 g(n) 提供了一个很好的,紧绑在 f(n) .

    我理解的方式是:

    • O(f(n)) 给出给定函数/算法的最坏情况复杂度。
    • Ω(f(n)) 给出给定函数/算法的最佳情况复杂性。
    • Θ(f(n)) 给出给定函数/算法的平均事例复杂度。

    如果我错了,请纠正我。如果是这样,每个算法的时间复杂性必须用这三个符号表示。但我观察到它的表达方式要么是O,_),要么是_,为什么这三个都不是?

    5 回复  |  直到 15 年前
        1
  •  35
  •   ShreevatsaR    15 年前

    重要的是要记住,符号,无论是O、_或_,表示 函数的渐近增长 ;它本质上与算法无关 本身 . 所讨论的功能 可以 是一个算法的“复杂性”(运行时间),无论是最坏情况、最佳情况还是平均情况,但是符号与函数的来源无关。

    例如,函数f(n)=3n +5是:

    • O(N) ,也是O(N) log n),O(n) (o)(n) )等等,但不是O(N)。
    • γ(n) ,也为_(n log n)、(n)等,但不是_(n) )
    • α(n) )它甚至不是(n 对数n)或_(n /log n)。

    现在,通常所考虑的函数是一个算法的最坏情况下的复杂度,使用哪种表示法来表示这三个函数取决于我们想说什么,以及我们如何仔细地进行分析。例如,我们可以观察到,由于有两个嵌套循环,最坏的运行时间是 最多 O(N) ,而不关心这是否是为某些输入实际实现的。(通常很明显)或者,我们可以说,排序的最坏运行时间是)(n log n),因为必须有一些输入,它必须至少采取cn(log n)步骤。或者,我们可以看一个特定的mergesort算法,在最坏的情况下,它最多需要O(n log n)个步骤。 一些输入使它采取n个log n步骤,所以最坏的运行时间是_(n log n)。

    请注意,在上述三个示例中,所分析的运行时间仍然相同(最坏的情况)。我们可以分析最佳情况或平均情况,但同样,我们使用的三个符号中的哪一个取决于我们想说的是是要给出一个上界、下界,还是对增长顺序的紧界。 相同的功能 .

        2
  •  33
  •   Jim Ferrans    15 年前

    _表示一个渐近紧的上界和下界。

    o表示上界,但这个界可能紧,也可能不紧。
    o表示不紧的上界。

    _)表示下限,但此界限可能或可能不紧密。
    _表示不紧的下限。

        3
  •  6
  •   codaddict    15 年前
        4
  •  6
  •   Steve Jessop    15 年前

    这三个词的意思是什么,请看伯克·G·德的回答。

    还要注意,它们与最佳情况、最坏情况和平均情况完全无关。例如,冒泡排序是_(n)最佳情况(因为如果数据已经排序,只需要n-1比较)和_(n^2)最差情况。假设输入随机洗牌,则为_(n^2)平均情况。因此,平均情况也是O(n^2)、O(n^3)和O(2^n)。

    哦,告诉你这是什么束缚。他们不会告诉你什么是界限。在上下文中,它可能是对最佳情况、最差情况、平均情况或整个算法(所有情况)的限制。

    当然,如果一个算法有(g)最佳情况,那么它本身就是(g)。如果它有O(G)最坏的情况是O(G)。所以这里有一种关系。但是,如果它有一个平均情况,这几乎不能告诉你最好和最坏的情况。

    至于“为什么三个都不呢?”.

    如果你的函数是_(g),那么它也是O(g)和_(g)。因此,在一个_______

    当你单独看到另一个,通常是因为我们只关心上界,或者我们只关心下界。所以我们说,所有的比较排序都必然是(n log n)最坏的情况,而气泡排序是(n^2)最坏的情况,但o(n)最好的情况,因为我们没有试图充分描述时间的复杂性,我们只是在表达我们在特定环境中关心的界限。

    无论如何,大多数人似乎都懒惰,不想打希腊字母。我知道我是。所以我们只说比较排序“最多是O(n log n)”。这确实是一种符号滥用,但它得到了重点。

        5
  •  0
  •   D_K    15 年前

    big-o表示法通常被称为算法的复杂性,因为它保证了算法在大n下不会表现得更差。然而,正如前面正确指出的,big-o给出了渐进性评估,当给定某个输入时,我们的算法可能表现出不同的行为。例如,当数组已经排序时,快速排序可以是o(n^2)。在实际应用中,渐近情况可能会得到改善,并得到很好的实现。