第5题:
问答题
在算法复杂性分析中,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、Ω、Θ分别提供了算法运行时间的上界、下界、平均。
解析:
暂无解析