试题详情
简答题在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况下，O、Ω、Θ分别提供了算法运行时间的什么界？
  • 如果存在两个正常数c和N0，对于所有的N≥N0，有|f（N）|≤C|g（N）|，则记作：f（N）=O（g（N））。这时我们说f（N）的阶不高于g（N）的阶。
    若存在两个正常数C和自然数N0，使得当N≥N0时有|f（N）|≥C|g（N）|，记为f（N）=Ω（g（N））。这时我们说f（N）的阶不低于g（N）的阶。
    如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g（N）|≤|f（N）|≤c2|g（N）|，则记作f（N）=（g，（N））。
    O、Ω、Θ分别提供了算法运行时间的上界、下界、平均。

  • 关注下方微信公众号，在线模考后查看

热门试题