哦vs大

可能重复:
Θ(n)和O(n)之间的区别是什么?

在我看来,当人们非正式地谈论算法的复杂性时,他们会谈论大 - 哦。 但在正式的情况下,我经常会看到偶尔会出现的大屁股。我从数学角度知道两者之间的区别,但在英语中,在什么情况下会使用大哦,当你的意思是大的时候不正确,反之亦然(示例算法将被赞赏)?

奖金:为什么人们在非正式谈话时似乎总是用得很大?


大O是一个上限。

Big-Theta是一个紧密的界限,即上限和下限。

当人们只担心可能发生的最坏情况时,大O就足够了; 即它说“它不会比这更糟糕”。 当然,边界越紧密越好,但紧密边界并不总是易于计算。

也可以看看

  • 维基百科/大O符号
  • 相关问题

  • Θ(n)和O(n)之间的区别是什么?

  • 以下来自维基百科的引用也显示出一些亮点:

    非正式地,特别是在计算机科学中,大O符号经常被允许有些滥用来描述渐近紧束缚,在某种情况下使用Big Theta符号可能更符合事实。

    例如,当考虑函数T(n) = 73n 3 + 22n 2 + 58 ,以下所有通常都是可接受的,但是绑定的紧密性(即下面的子弹2和3)通常强烈地优于绑定的松弛度即下面的子弹1)。

  • T(n) = O(n 100 ) ,与T(n) ∈ O(n 100 )
  • T(n) = O(n 3 ) ,这与T(n) ∈ O(n 3 )
  • T(n) = Θ(n 3 ) ,其与T(n) ∈ Θ(n 3 )
  • 相应的英语语句分别是:

  • T(n)渐近地增长不超过n 100
  • T(n)渐近地增长不会快于n 3
  • T(n)n 3一样快地增长。
  • 因此,尽管所有三个陈述都是真实的,但每个陈述都包含越来越多的信息。 然而,在某些领域,Big O符号(上面列表中的第2号子弹)比Big Theta符号更常用(上面列表中的第3号子弹),因为增长更慢的函数更可取。


    我是一名数学家,而且我一次又一次地看到并需要大O,大-Theta和大Omega符号,而不仅仅是算法的复杂性。 正如人们所说,大泰塔是一个双向的界限。 严格地说,当你想解释算法能做得多好时,你应该使用它,或者那个算法不能做得更好,或者没有算法能做得更好。 例如,如果你说“排序需要Θ(n(log n))比较最坏情况下的输入”,那么你解释说有一个排序算法使用O(n(log n))比较任何输入; 并且对于每个排序算法,都有一个强制它进行Ω(n(log n))比较的输入。

    现在,人们使用O代替Ω的一个狭义理由是放弃关于最差或平均情况的免责声明。 如果你说“排序需要O(n(log n))比较”,那么该语句对于有利的输入仍然适用。 另一个狭义的原因是,即使一个算法做X需要时间Θ(f(n)),另一个算法可能会更好,所以你只能说X本身的复杂性是O(f(n))。

    然而,更广泛的原因是,人们非正式地使用O.在人的层面上,当反面从背景中“显而易见”时总是做出双面陈述是一种痛苦。 因为我是一名数学家,所以我理想的时候总是要小心地说,“只要下雨,我就会带雨伞”或者“我可以玩弄4个球而不是5个”,而不是“我会拿伞,如果它降雨“或”我可以玩弄4个球“。 但是另一半的这种言论通常显然是有意或无意的。 显而易见,这只是人为天性。 把头发分开是令人困惑的。

    不幸的是,在数学或算法理论等严格的领域,它也混淆不去分割头发。 当他们应该说Ω或Θ时,人们将不可避免地说出O. 跳过细节是因为它们“显而易见”总是会导致误解。 对此没有解决方案。


    因为我的键盘有一个O键。
    它没有Θ或Ω键。

    我怀疑大多数人都是懒惰的,当他们指Θ时使用O,因为它更容易输入。

    链接地址: http://www.djcxy.com/p/6829.html

    上一篇: oh vs big

    下一篇: Theta and Big O notation in simple language