具有不同复杂度的算法

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)下有界界定。