下面的集合有10个元素
{10, 20, 21, 22, 23, 40, 50, 56, 90, 100}
N = 10 O(日志 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)？
最佳答案
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) .
关于algorithm - 10 个元素的二进制搜索复杂度是 0(log 10) = 1 ，但所需的比较是 4，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28505100/