二进制搜索与顺序搜索/盈亏平衡点

Question

我真的很纠结于这个家庭作业问题。我的教授在解释任何事情方面做得很糟糕。帮助?

排序列表与使用二进制搜索与仅对未排序的列表使用顺序搜索之间存在权衡。选择取决于搜索列表的次数。假设序列搜索在最坏的情况下需要n个比较，排序需要n*log n比较，二进制搜索在最坏的情况下需要log n比较(正如我们已经讨论过的，其中log是log基2 )。给定一个由1024个元素组成的未排序列表(即log 1024 = 10)，需要多少搜索才有价值？假设我们考虑序列搜索的平均情况需要n/2比较。现在，s的盈亏平衡点是什么？ 提示:为每个方法搜索s所需的比较数编写一个表达式；然后将它们设为相等并为s求解。

Answer 1

您正在比较执行初始排序(成本：n*log(n))和后续二进制搜索(成本：log(n))所需的时间。因此，如果您想搜索s时间，您将为每个(二进制)搜索支付一个初始的n*log(n)来排序列表和log(n)。这就是说：

c1 = (n*log(n)) + (s*log(n)) = (n+s)*log(n)

相反，如果执行线性搜索，则不存在“初始成本”，但每次搜索都将花费n，因此对于s搜索：

c2 = s*n

显然，对于足够小的s和n，c2更小，因为没有这样的初始成本，但它的增长速度比c1快。在一定程度上，c1和c2会交叉。也就是说，c1 = c2。

                                                                     n * log(n)
s * n = (n + s) * log(n) --> s * (n - log(n)) = n * log(n) --> s = ------------
                                                                     n - log(n)

好吧，你现在必须讨论上面的方程式。这个阴谋应该告诉你一切：

​

​

Answer 2

提示:对n排序然后执行k个二进制搜索的工作由

N log n+k log n

执行k个顺序搜索所需的工作是

恩克

如果n= 1,000，那么第二个量比第一个量小多少？

希望这能有所帮助！