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

符号的辨析

Ο,读音: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)$

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

以前就只知道要忽略常数

1 条评论
  1. I am just writing to let you know what a impressive experience my daughter undergone browsing your site. She learned a lot of pieces, with the inclusion of what it is like to have an awesome helping nature to let the mediocre ones smoothly grasp several complicated subject matter. You truly surpassed my expectations. Many thanks for imparting the valuable, trusted, explanatory as well as fun thoughts on your topic to Mary.

发表一条评论