10个元素的二进制搜索复杂度为0(log 10)= 1,但所需的比较为4

Question

以下集合包含10个元素

{10, 20, 21, 22, 23, 40, 50, 56, 90, 100}

N = 10 O(log 10)= 1

如果必须搜索元素20,则必须执行4次比较操作(即)

1-comparision  10
2-comparision 23 (since mid value of 10 elements)
3-comparision 21 (mid)
4-comparision 20

二进制搜索如何具有O(log N)的复杂性？

Answer 1

Big-oh表示法并不关心常量.事实上,除了表达中的主导词之外,它并不关心任何事情.

因此,即使您的算法执行4 * log n某种类型的操作,它仍然是O(log n).只要它是一个恒定的时间f(n),复杂性将是O(f(n)).

对于对数,基数是无关紧要的,因为给定基数中的对数与不同基数中的相同对数不同.这可以通过基本更改公式看出:

log_a(x) = log_b(x) / log_b(a)
         = [1 / log_b(a)] * log_b(x)
           \____________/
          this is constant

这就是为什么通常不用大写符号指定基数的原因.

请注意,如果您将输入的大小乘以一个数量级,使其成为100元素,那么您将执行<= 8此类操作,即4 * log_10(100).