big-o - 了解何时使用 theta 来计算时间复杂度

Question

我（相信）我了解 Big-O、Big-Ω 和 Big-Θ 的定义；其中 Big-O 是渐近上界，Big-Ω 是渐近下界，Big-Θ 是渐近紧界。但是，我一直对在某些情况下使用 Θ 感到困惑，例如在插入排序中：

据我了解，这表明插入排序将：

1. 至少花费线性时间（它不会比线性时间运行得更快）；根据大Ω。

2. 最多n^2花费时间（不会超过n^2）；根据Big-O。

困惑源于我对何时使用 Big-Θ 的理解。为此，我被引导相信只有在 Big-O 和 Big-Ω 的值相同时才能使用 Big-Θ。如果是这样，为什么插入排序被认为是Θ(n^2)当Ω和O值不同时？

标签： big-ocomplexity-theory

Answer 1

基本上，只有在算法运行时间的上限和下限之间没有渐近间隙时，才能使用 Big-Θ：

在您的示例中，插入排序最多需要 O(n^2) 时间（在最坏的情况下），并且需要 Ω(n) 的时间（在最好的情况下）。因此，O(n^2) 是算法的时间上限，Ω(n) 是算法的下限。由于这两个不相同，因此您不能使用 Big-Θ 来描述插入排序算法的运行时间。

但是，请考虑选择排序算法。它最坏情况下的运行时间是O(n^2)，最好情况下运行时间是Ω(n^2)。因此，由于上界和下界相同（渐近），可以说选择排序算法的运行时间为 Θ(n^2)。