algorithm - 为什么要考虑二分查找运行时间复杂度为log2N

Question

谁能解释一下二分查找的运行时间复杂度是 O(log n)？我在 Google 中搜索并得到以下内容，

"The number of times that you can halve the search space is the same as log₂ n".

我知道在数据结构中找到搜索键之前我们会减半，但为什么我们必须将其视为 log₂ n？我知道 e^x 是指数增长，所以 log₂ n 是二进制衰减。但是我无法根据对数定义的理解来解释二分搜索。

Answer 1

可以这样想:

如果你能负担得起 m 次的一半，(即，你能负担得起与 m 成正比的时间)，那么你能负担得起搜索多大的数组？

显然是 2^m 大小的数组，对吧？

因此，如果您可以搜索大小为 n = 2^m 的数组，那么它所花费的时间与 m 成正比，并且求解m 对于 n 看起来像这样:

n = 2^米

log₂(n) = log₂(2^m)

log₂(n) = 米


换句话说:对大小为 n = 2^m 的数组执行二分搜索所花费的时间与 m 成正比，或者等效地，与 < em>log₂(n).