渐进符号 - O()、o()、Ω()、ω() 和 θ()

渐进符号

渐进符号用于表示算法在渐进分析中的复杂度。这些符号是表示复杂度的数学工具。常用的有三种符号。

大O符号

大O (O) 符号给出了函数 f(n) 的一个上界，精确到一个常数因子。

小o符号

除了大O、大Ω和大Θ符号外，还有一些其他的符号。小o符号就是其中之一。

小o符号用于描述一个不能收紧的上界。换句话说，它是f(n) 的一个宽松上界。

大Ω符号

大Ω (Ω) 符号给出了函数 f(n) 的一个下界，精确到一个常数因子。

小ω符号

另一个渐进符号是小ω符号，表示为 (ω)。

小ω (ω) 符号用于描述 f(n) 的一个宽松下界。

大Θ符号

大Θ(Θ) 符号给出了函数 f(n) 的一个界限，精确到一个常数因子。

Arnab Chakraborty

更新于：2019年8月5日

7K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习