Big-oh vs big-theta [重复]

Big-oh vs big-theta [重复]

Big-O是一个上限。

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

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

也可以看看

• 维基百科/大O符号

---

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

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

例如，当考虑函数

T(n) = 73n

3

+ 22n

2时

+58

，通常所有以下条件都是可以接受的，但是通常强烈地希望装订的紧密度（即下面的项目符号2和3）优于松紧的装订度（即下面的项目符号1）。

1. T(n) = O(n

   100

   )

   ，等于

   T(n) ∈ O(n

   100

   )

2. T(n) = O(n

   3

   )

   ，与3相同

   T(n) ∈ O(n``)

3. T(n) = Θ(n

   3

   )

   ，与3相同

   T(n) ∈ Θ(n``)

   
   
   

等效的英语陈述分别是：

1. T(n)

   渐近增长不超过

   n

   100

2. T(n)

   渐近增长不超过

   n

   3

3. T(n)

   渐近地增长到

   n

   3。
   
   

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