1

试图围绕一些基本和常见的算法来思考..我目前对这个问题的理解是粗体的。

(1) 假设我们有一个有n个元素的排序数组：二分查找最多比较元素多少次？

我一直看到'0（log（n））'作为此类问题的一般答案弹出，但我不明白为什么。没有一个整数可以回答这个问题（即 2 还是 3？）

(2) 假设我们有一个包含n项的数组：线性搜索最多比较元素多少次？

同样，与上面相同，但现在“ 0(n) ”似乎是这个问题的一般答案。同样，我不太了解这个答案背后的力量，并质疑为什么没有整数答案？

(3) 有人可以解释一个线性搜索比二分搜索更好的例子吗？

从我收集的信息来看，如果可能的话，通常二进制搜索似乎是一个更好的选择，因为它的速度很快。我很难看到线性搜索何时会是更好的选择。

4

4 回答 4

3

关于 1 和 2，如果提供绝对数作为输入的大小，则可以使用绝对数作为答案。由于问题询问了一个任意大小的数组（长度n），因此也以这些术语给出了答案。
您可以阅读更多关于大 O 表示法的详细信息，但基本上O(n)&O(log n)表示order of n&order of log(n)分别。即，例如，如果输入大小为 100，则使用线性搜索比较元素的数量也将在 100 左右，而使用二分搜索则需要比较 ~ log(100) 个元素。
至于3，二分查找需要对输入进行排序...

于 2015-05-03T15:29:25.430 回答
1

O 符号是关于限制行为的。所以二分查找将列表分成两部分。要么您找到了该项目，要么您有一半要搜索。因此 O(nlogn) 的限制行为 - 即在搜索树的叶子处。

线性搜索只是从头开始。最糟糕的可以（限制）是元素在最后）。

对于 (3)，如果该项目是列表中的第一个，则您中了大奖。所以在那种情况下会更好

于 2015-05-03T15:36:51.460 回答
1

首先，您正在处理 O 表示法，因此不可能使用“整数”。答案的O(f(n))格式始终f(n)为n. 如果您不确定 Big O 符号的全部含义，那么从http://en.wikipedia.org/wiki/Big_O_notation开始可能会有所帮助。

(1) 对有序数组进行二分查找，搜索空间反复减半，直到找到该项。如果我们考虑一个理想的二分搜索实现，其中每个操作都需要恒定的时间，在最坏的情况下，我们将需要检查近似logn项目 - 这将需要O(logn)时间。至于背后的数学logn：它们并不难，但很难在 iPhone 上输入。提示：谷歌是你的朋友。

(2) 在对未排序数组进行线性搜索时，我们可能必须检查数组中的每一项。同样，这是一种简化，但假设我们算法中的每个操作都需要恒定时间，我们必须至少查看n次数。因此O(n)。

(3) (1) 和 (2) 中必须搜索的数据有什么不同？请记住，排序是最优的O(nlogn)。

于 2015-05-03T15:53:39.523 回答
0

以下视频提供了全面的解释。我希望它能帮助你理解二分搜索和线性搜索之间的区别。

对于问题3：

  • 二进制搜索需要排序的序列。
  • 对于序列 1,2,3,...,100。当你想找到元素 1 时，线性搜索会更快。它只会检查第一个元素。
于 2015-05-03T15:41:18.690 回答