请教：该算法的Big Oh、Big Omega和Big Theta复杂度是多少？

结合《算法设计手册》中这类典型的算法问题，我们可以这样分析：

• 首先确认你判断的*O(nlogn)*是否准确：如果该算法是类似归并排序这类分治算法（递归式满足T(n) = 2T(n/2) + O(n)），那么上界O(nlogn)是正确的。
• Big Omega（Ω）：对于基于比较的排序这类问题，下界是Ω(nlogn)——也就是说任何这类算法在最坏或平均情况下，至少需要完成Ω(nlogn)次基本操作。如果你的目标算法属于这类，那它的Ω就是Ω(nlogn)。
• Big Theta（Θ）：当算法的上界O(f(n))和下界Ω(f(n))完全一致时，Θ(f(n))就是它的紧确时间复杂度。所以如果这个算法的O(nlogn)和Ω(nlogn)都成立，那么它的Θ就是Θ(nlogn)。

简单来说：如果你的O(nlogn)判断正确，且该算法无法以低于nlogn的时间完成（这在多数分治类核心算法中都是成立的），那么它的Big Omega是Ω(nlogn)，Big Theta是Θ(nlogn)。

内容的提问来源于stack exchange，提问作者Michele