为什么在所有情况下，特别是二分搜索在 O(log n) 时间内 运行 而不是 Θ(log n) 时间？
Why specifically does a binary search, in all cases, run in O(log n) time, but not Θ(log n) time?
我理解，在二分查找最佳情况的特定场景中，运行 时间图（一条常量线）不能低于对数函数的任何倍数（因为对数接近无穷大因为 n 接近无穷大），这使得 Θ(log n) 不适用于最佳情况的描述，因此说 Θ(log n) 描述所有情况[=18 的运行时增长是错误的=] 的二进制搜索。
我的推理是否正确？
如果是这样，这是否意味着我们在使用 bigO/theta/omega 表示法时总是在描述一组隐含的情况？例如，如果有人说一个算法在 O(n^2) 时间内运行，他们是否隐含地意味着该算法在所有情况（最佳、最差和平均）、部分情况（例如最差和平均，但不是最好的）或特定情况？换句话说，这是否意味着算法没有“一般”bigO/theta/omega描述，仅针对算法的特定情况（有时可能会发生所有情况可能被描述为相同的情况）？
我会说你的推理是正确的。二进制搜索 not Θ(log n) for every case.
下列说法正确的是：
- 每种情况都是 O(log n)。
- 在最坏的情况下是Θ(log n)。
- 平均为 Θ(log n)。
然而（这是一个解释问题），我也可能会原谅有人说：
- 是Θ(log n)。
因为通常会假定平均值或 worst-case。但是就像你说的那样，并非对所有情况都是如此，因为对于特定输入，二进制搜索可以 运行 in O(1).
使用 big-O 表示法的好处是，与 big-Θ 不同，它表达了复杂性的上限，这意味着我们可以用它来表示例如算法速度很快，而不必关心琐碎或“幸运”的情况等等。如果你在 O(n2) 中说一个算法 运行s，它通常意味着 worst-case，因为这样边界将适用于所有情况。如果不是，您倾向于指定它是例如仅平均情况，例如经常为快速排序所做的。这就是为什么在列出算法复杂性时，您通常会看到 big-O 而不是 big-Θ，例如在 Wikipedia 页面上进行二进制搜索。
我理解，在二分查找最佳情况的特定场景中，运行 时间图（一条常量线）不能低于对数函数的任何倍数（因为对数接近无穷大因为 n 接近无穷大），这使得 Θ(log n) 不适用于最佳情况的描述，因此说 Θ(log n) 描述所有情况[=18 的运行时增长是错误的=] 的二进制搜索。
我的推理是否正确？
如果是这样，这是否意味着我们在使用 bigO/theta/omega 表示法时总是在描述一组隐含的情况？例如，如果有人说一个算法在 O(n^2) 时间内运行，他们是否隐含地意味着该算法在所有情况（最佳、最差和平均）、部分情况（例如最差和平均，但不是最好的）或特定情况？换句话说，这是否意味着算法没有“一般”bigO/theta/omega描述，仅针对算法的特定情况（有时可能会发生所有情况可能被描述为相同的情况）？
我会说你的推理是正确的。二进制搜索 not Θ(log n) for every case.
下列说法正确的是：
- 每种情况都是 O(log n)。
- 在最坏的情况下是Θ(log n)。
- 平均为 Θ(log n)。
然而（这是一个解释问题），我也可能会原谅有人说：
- 是Θ(log n)。
因为通常会假定平均值或 worst-case。但是就像你说的那样，并非对所有情况都是如此，因为对于特定输入，二进制搜索可以 运行 in O(1).
使用 big-O 表示法的好处是，与 big-Θ 不同，它表达了复杂性的上限，这意味着我们可以用它来表示例如算法速度很快，而不必关心琐碎或“幸运”的情况等等。如果你在 O(n2) 中说一个算法 运行s，它通常意味着 worst-case，因为这样边界将适用于所有情况。如果不是，您倾向于指定它是例如仅平均情况，例如经常为快速排序所做的。这就是为什么在列出算法复杂性时，您通常会看到 big-O 而不是 big-Θ，例如在 Wikipedia 页面上进行二进制搜索。