我在考试时遇到了这个问题，
我有一台非常慢的计算机，对具有 1,000(一千)个元素的数组进行二分搜索需要一秒钟。我应该期望计算机在具有 1,000,000(一百万)个元素的数组上进行二分搜索需要多长时间？
我无法理解这一点，搜索 100 万个元素会比搜索 1,000 个元素花费更长的时间，还是取决于计算机？
最佳答案
二分查找的时间复杂度为O(log(N))，完成时间为
t = c * log(N, 10)
在给定的N = 1000情况下，我们知道t，因此我们可以找出c
1 = c * log(1000, 10)
1 = c * 3
c = 1/3
对于N = 1000000，我们有
t = 1 / 3 * log(1000000, N) =
= 1 / 3 * 6 =
= 2
因此我们可以预期 1000000 项内的二分搜索将在 2 秒内完成。
请注意，O(log(N)) == O(log(N, m))，因为 log(N, m) == log(N, k)/log(m, k)，这意味着在使用 O(log(N)) 时，我们可以自由选择对数底数。在我们的例子中(1000 和 1000000)，使用基数 10(或 1000)会很方便
关于algorithm - 通过多个元素进行二分查找，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69921477/