Θ,既是上界也是下界(tight),等于的意思。

O符号是用于描述函数渐近行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。

Ω符号的定义与O符号的定义类似,但主要区别是,O符号表示函数在增长到一定程度时总小于一个特定函数的常数倍,大Ω符号则表示总大于,来描述一个函数数量级的渐近下界。

Θ符号是O符号和Ω符号的结合。下面给出具体的数学定义:

函数\(f ( n )\)代表某一算法在输入大小为n的情况下的工作量(效率),则在n趋向很大的时候,我们将f (n)与另一行为已知的函数g(n)进行比较: