algorithm - 渐近界与运行时间之间的关系？

Question

以二分查找为例，最好的情况运行时间会在第一次比较时得到

key_to_find == (imin + imax) / 2;

最佳情况下的运行时间将由 O(1) 表示。我完全理解，但令我困惑的是为什么使用 O(1) 以及为什么我不能使用 Θ(1) 或任何其他相同的表示法。

即如何确定我应该使用哪种表示法来表示运行时间(最佳、平均或最差情况)。

Answer 1

O 表示法和 Θ 表示法与最佳情况、平均情况或最坏情况没有直接关系。它们用于函数的渐近边界。你可以写:47n lg n = O(n lg n),3n^2 + 4n = O(n^2)

并且 O 和 Θ 符号之间存在差异。 O 表示“最多(使用一些常数因子)”，Θ 表示“相等(使用一些常数因子)”，例如:47n ln n = O(n^2)，但不是 Θ(n^2)。

如果你想表达最佳情况、平均情况或最坏情况，你通常会显式地写出来:“最佳情况是 O(1)(或 Θ(1))，平均情况是 O(lg n)，最坏情况是 O(n)。”

有时候你也“运行时间是O(x)”，那么你的意思是，运行时间至多与x成正比。如果你说“运行时间是 Θ(x)”，那么你的意思是，运行时间总是与 x 成正比。