时间戳

首页 > 解决方案 > 通过多个元素进行二分搜索

algorithm - 通过多个元素进行二分搜索

问题描述

考试的时候有这个问题

我有一台非常慢的计算机，它需要一秒钟的时间对具有 1,000（一千）个元素的数组进行二进制搜索。我应该期望计算机在具有 1,000,000（一百万）个元素的数组上进行二分搜索需要多长时间？

我很难理解这一点，搜索 100 万个元素会比 1,000 个元素花费更长的时间还是取决于计算机？

标签： algorithmtime-complexitybinary-search

解决方案

二分查找具有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))我们可以自由选择对数底。在我们的例子中 ( 1000and 1000000) 使用 base 10(or 1000)很方便

推荐阅读