【入门难度】时间复杂度符号的辨析

符号的辨析

Ο,读音:big-oh;表示渐进上界,小于等于。
ο,读音:small-oh;表示上界,小于。
Ω,读音:big omega、欧米伽;表示渐进下界,大于等于。
ω,读音:small omega;表示下界,大于。
Θ,读音:theta、西塔;既是上界也是下界,称为确界,等于。


Ο是渐进上界,Ω是渐进下界。Θ需同时满足大Ο和Ω,故称为确界。Ο极其有用,因为它表示了最差性能。

对于一个算法来说,我们常常需要计算其复杂度来决定我们是否选择使用该算法。 对于一个算法,假设其问题的输入大小为n,那么我们可以用 O(n) 来表示其算法复杂度(time complexity)。
那么,渐进时间复杂度(asymptotic time complexity)
就是当n趋于无穷大的时候,O(n)得到的极限值。

大O大Ω都是当N趋于无穷时的结果。意思就是可以忽略常数。


举一个具体的例子
$o(3n^2+52)=O(n^2)$

蒟蒻表示刚懂(因为刚学完极限)

以前就只知道要忽略常数

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注