在我看来,当人们非正式地谈论算法复杂性时,他们谈论的是“大哦”。但是在正式情况下,我经常看到大θ偶尔会被扔进去。我从数学上知道两者之间的区别是什么,但是用英语,在什么情况下,当您说大θ被用作大θ时错误,反之亦然(示例算法将不胜感激)?
奖励:为什么人们在非正式交谈中似乎总是使用big-oh?
Big-O是一个上限。
Big-Theta是一个严格的界限,即上限 和 下限。
当人们只担心可能发生的最坏情况时,big-O就足够了。即它说“它不会比这更糟”。当然,界限越小越好,但是界限并不总是容易计算的。
Wikipedia的以下引述也有一些启示:
非正式地,尤其是在计算机科学中,通常允许使用Big O表示法来描述渐近紧界,而在给定的背景下使用Big Theta表示法实际上更为合适。 例如,当考虑函数T(n) = 73n3 + 22n2时+ 58,通常所有以下条件都是可以接受的,但是通常强烈地希望装订的紧密度(即下面的项目符号2和3)优于松紧的装订度(即下面的项目符号1)。 T(n) = O(n100),等于T(n) ∈ O(n100) T(n) = O(n3),与3相同T(n) ∈ O(n``) T(n) = Θ(n3),与3相同T(n) ∈ Θ(n``) 等效的英语陈述分别是: T(n)渐近增长不超过n100 T(n)渐近增长不超过n3 T(n)渐近地增长到n3。 因此,尽管这三个陈述都是正确的,但每个陈述中都包含越来越多的信息。但是,在某些领域中,Big O表示法(上面列表中的项目符号编号2)比Big Theta表示法(上面列表中的项目符号编号3)更常用,因为更希望函数增长得更慢。
非正式地,尤其是在计算机科学中,通常允许使用Big O表示法来描述渐近紧界,而在给定的背景下使用Big Theta表示法实际上更为合适。
例如,当考虑函数T(n) = 73n3 + 22n2时+ 58,通常所有以下条件都是可以接受的,但是通常强烈地希望装订的紧密度(即下面的项目符号2和3)优于松紧的装订度(即下面的项目符号1)。
T(n) = 73n
+ 22n
+ 58
T(n) = O(n
)
T(n) ∈ O(n
T(n) ∈ O(n``)
T(n) = Θ(n
T(n) ∈ Θ(n``)
等效的英语陈述分别是:
T(n)
n
因此,尽管这三个陈述都是正确的,但每个陈述中都包含越来越多的信息。但是,在某些领域中,Big O表示法(上面列表中的项目符号编号2)比Big Theta表示法(上面列表中的项目符号编号3)更常用,因为更希望函数增长得更慢。