算法具有不同的复杂性

Question

算法的复杂性可以在O(n ^ 2)和O(n logn)中吗？我很确定这个.但是在Ω(n ^ 2)和O(n logn)中,还是在Θ(n ^ 2)和Ω(n logn)中呢.谢谢

Answer 1

1. Big-O表示法仅指上限.因此,如果它在O(n log n),它必然在O(n^2)(因为n^2增长得快n log n).

2. 不,它不能同时?(n^2)存在O(n log n).这意味着"上限受限于n log n下限n^2,这是不可能的.

3. ?(n^2)意味着它在上下都有界限n^2,这必然意味着它在下面被限制?(n log n).