time-complexity - 为什么二分查找在所有情况下都在 O(log n) 时间内运行，而不是在 Θ(log n) 时间内运行？

Question

我理解，在二分搜索最佳情况的特定场景中，运行时间图(一条常量线)不能低于对数函数的任何倍数(因为当 n 接近无穷大时对数接近无穷大)，这使得 Θ(log n) 不适用于最佳情况的描述，因此说 Θ(log n) 描述了二分查找所有情况的运行时增长是错误的。

我的推理是否正确？

如果是这样，这是否意味着在使用 bigO/theta/omega 符号时，我们总是在描述一组隐含的情况？例如，如果有人说一个算法在 O(n^2) 时间内运行，他们是否隐含地意味着该算法在所有情况(最佳、最差和平均)、部分情况(例如最差和平均，但不是最好的)或特定情况？换句话说，这是否意味着算法没有“通用的”bigO/theta/omega 描述，仅适用于算法的特定情况(有时可能会发生所有情况可能被描述为相同的情况)？

Answer 1

我会说你的推理是正确的。二分搜索不是 Θ(log n) 每个 情况。

下列说法正确的是:

• 每种情况都是 O(log n)。
• 在最坏的情况下是Θ(log n)。
• 平均Θ(log n)。

但是(这是一个解释问题)，我也可以原谅有人说:

• 是Θ(log n)。

因为通常会假设平均情况或最坏情况。但正如您所说，并非所有情况都适用，因为对于特定输入，二进制搜索可以在 O(1) 内运行。

与大 O 符号相反，大 O 符号的好处在于它表达了复杂性的上限，这意味着我们可以用它来表示例如算法速度很快，而不必关心琐碎或“幸运”的情况等等。如果你说一个算法在 O(n²) 中运行，它通常意味着最坏的情况，因为边界将适用于所有情况。如果不是，您倾向于指定它是例如仅平均情况，例如经常为快速排序所做的。这就是为什么在列出算法复杂性时，您通常会看到使用 big-O 而不是 big-Θ，例如在维基百科页面上进行二进制搜索。