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

Question

以下集合有10个元素

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

N=10O（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（logn）。只要它是f(n)的常数倍，复杂度就会是O(f(n))。

对于对数，底是不相关的，因为给定底中的对数与不同底中的同一对数相差一个常数。这可以从基数变化公式中看出：

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

这就是为什么在大oh表示法中通常不指定基数的原因。

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

Answer 2

在一般情况下，复杂性的顺序实际上并不意味着要评估为一个精确的数字。除此之外，使用的对数是变量的二进制log_2，而不是十进制对数。

请注意，您每次都将问题减半，而不是将其减少到十分之一。诚然，就复杂性分析而言，所有日志彼此之间只有一个恒定的乘数，因此无关紧要，但我认为这与您的问题有关。