哦vs大
可能重复:
Θ(n)和O(n)之间的区别是什么?
在我看来,当人们非正式地谈论算法的复杂性时,他们会谈论大 - 哦。 但在正式的情况下,我经常会看到偶尔会出现的大屁股。我从数学角度知道两者之间的区别,但在英语中,在什么情况下会使用大哦,当你的意思是大的时候不正确,反之亦然(示例算法将被赞赏)?
奖金:为什么人们在非正式谈话时似乎总是用得很大?
大O是一个上限。
Big-Theta是一个紧密的界限,即上限和下限。
当人们只担心可能发生的最坏情况时,大O就足够了; 即它说“它不会比这更糟糕”。 当然,边界越紧密越好,但紧密边界并不总是易于计算。
也可以看看
相关问题
以下来自维基百科的引用也显示出一些亮点:
非正式地,特别是在计算机科学中,大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