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

在一般情况下，复杂度的顺序并不是真的要评估为一个确切的数字。除此之外，使用的日志是变量的二进制 log_2，而不是十进制对数。

请注意，您每次都将问题减半，而不是将其削减为十分之一。不可否认，就复杂性分析而言，所有日志彼此之间只是一个常数乘数，因此无关紧要，但我认为这切入了你的问题。

Answer 2

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

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

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

Binary search complexity for 10 elements is 0(log 10) = 1 , but the comparision required are 4