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

Question

让我们以二分搜索为例，最好的情况下运行时间将在第一次比较中获得

key_to_find == (imin + imax) / 2;

最佳案例运行时间将由 O(1) 表示。我完全理解这一点，但让我感到困惑的是为什么使用 O(1) 以及为什么我不能使用 Θ(1) 或任何其他表示法。

IE 。如何确定我应该使用哪种表示法来表示运行时间（最佳、平均或最坏情况）。

Answer 1

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

O a Θ 表示法之间存在差异。O 表示“最多（使用某个常数因子）”，Θ 表示“等于（使用某个常数因子）”，例如：47n ln n = O(n^2)，但它不是 Θ(n^2)。

如果你想表达最好的情况、平均的情况或最坏的情况，你通常会明确地写出来：“最好的情况是O(1)(或Θ(1))，平均的情况是O(lg n)，最坏的情况是O( n)。”

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

Answer 2

你可以使用任何你想要的符号。Big Theta 是最精确的，因此您应该随时使用它。作为旁注，在复杂性分析的上下文中，O(1) 等价于 Θ(1)（其中操作的数量是整数，即不能将 O(1/n) 作为复杂度）。