一尘不染

Big-oh vs big-theta [重复]

algorithm

在我看来,当人们非正式地谈论算法复杂性时,他们谈论的是“大哦”。但是在正式情况下,我经常看到大θ偶尔会被扔进去。我从数学上知道两者之间的区别是什么,但是用英语,在什么情况下,当您说大θ被用作大θ时错误,反之亦然(示例算法将不胜感激)?

奖励:为什么人们在非正式交谈中似乎总是使用big-oh?


阅读 239

收藏
2020-07-28

共1个答案

一尘不染

Big-O是一个上限。

Big-Theta是一个严格的界限,即上限 下限。

当人们只担心可能发生的最坏情况时,big-O就足够了。即它说“它不会比这更糟”。当然,界限越小越好,但是界限并不总是容易计算的。

也可以看看


Wikipedia的以下引述也有一些启示:

非正式地,尤其是在计算机科学中,通常允许使用Big O表示法来描述渐近紧界,而在给定的背景下使用Big Theta表示法实际上更为合适。

例如,当考虑函数T(n) = 73n3 + 22n2时+ 58,通常所有以下条件都是可以接受的,但是通常强烈地希望装订的紧密度(即下面的项目符号2和3)优于松紧的装订度(即下面的项目符号1)。

  1. T(n) = O(n100),等于T(n) ∈ O(n100)
  2. T(n) = O(n3),与3相同T(n) ∈ O(n``)
  3. T(n) = Θ(n3),与3相同T(n) ∈ Θ(n``)

等效的英语陈述分别是:

  1. T(n)渐近增长不超过n100
  2. T(n)渐近增长不超过n3
  3. T(n)渐近地增长到n3。

因此,尽管这三个陈述都是正确的,但每个陈述中都包含越来越多的信息。但是,在某些领域中,Big O表示法(上面列表中的项目符号编号2)比Big
Theta表示法(上面列表中的项目符号编号3)更常用,因为更希望函数增长得更慢。

2020-07-28