search - 二分搜索 - 最坏/平均情况

标签 search big-o time-complexity complexity-theory binary-search

我发现很难理解为什么/如何使用二分搜索在数组/列表中搜索键的最坏和平均情况是 O(log(n))。

log(1,000,000) 只有 6。log(1,000,000,000) 只有 9 - 我明白了,但我不明白解释。如果没有测试,我们怎么知道平均/最坏情况实际上是 log(n)?

希望大家能明白我想表达的意思。如果没有,请告诉我,我会尝试以不同的方式解释。

最佳答案

最坏情况

每次二分搜索代码做出决定时,它都会从考虑中消除一半的剩余元素。因此,您需要将每个决策的元素数量除以 2。

在只剩下一个元素之前,你能除以 2 多少次?如果 n 是元素的起始数量,x 是除以 2 的次数,我们可以将其写为:

n/(2 * 2 * 2 * ... * 2) = 1 [“2”重复 x 次]

或者,等价地,

n/2^x = 1

或者,等价地,

n = 2^x

因此,以 n 为底的对数为 2,得到 x,即做出的决策数。

最后,你可能会问,如果我使用以 2 为底的 log,为什么像你那样写成以 10 为底的 log 也可以呢?基数并不重要,因为差异是 only a constant factor它被大 O 表示法“忽略”。

平均情况

我看到你也问了平均情况。考虑:

  1. 第一次尝试时只能找到数组中的一个元素。
  2. 第二次尝试时只能找到两个元素。 (因为第一次尝试后,我们要么选择了右半部分,要么选择了左半部分。)
  3. 第三次尝试时只能找到四个元素。

您可以看到模式:1, 2, 4, 8, ... , n/2。要表达朝另一个方向的相同模式:

  1. 一半的元素需要进行最大数量的决策才能找到。
  2. 四分之一的元素需要更少的决策才能找到。
  3. 等等

由于一半元素花费的时间最长,因此其他元素花费的时间少多少并不重要。我们可以假设所有元素都花费最大时间,即使其中一半实际上花费 0 时间,无论真实平均值是多少,我们的假设都不会超过两倍。我们可以忽略“double”,因为它是一个常数因子。因此,就大 O 表示法而言,平均情况与最坏情况相同。

关于search - 二分搜索 - 最坏/平均情况,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29972735/

相关文章:

c# - 如何根据搜索词在结果中的位置指定 NHibernate 搜索结果的排名?

python - 发现我的代码的复杂性

algorithm - 顺序搜索时间中的预期搜索时间

algorithm - 在 O(n) 中证明图灵机计数?

java - 力扣 : Partition array according to a pivot

c# - 使用Windows搜索文件API

python - 搜索函数python

c# - Find() 与列表上的枚举

algorithm - 为什么这个算法复杂度为 O(n^2)?

time-complexity - 快速 (O(nlogn)) 约束 Delaunay 三角剖分算法