algorithm - 不同复杂度的算法

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)。