首页 文章

穷举搜索与排序，然后是二分搜索

提问于
浏览 次
4

这是G. Michael Scneider和Judith L. Gersting的教科书“计算机科学邀请”的直接引用 .

在3.4.2节的最后，我们讨论了在未排序列表上使用顺序搜索而不是对列表进行排序然后使用二进制搜索之间的权衡 . 如果列表大小为n = 100,000，那么在第二种替代方案在比较次数方面更好之前必须进行多少次最坏情况搜索？

我真的没有得到问题的要求 .

顺序搜索是有序（n），二进制是有序的（lgn），无论如何lgn总是小于n . 在这种情况下，已经给出了n，所以我应该找到什么 .

这是我的家庭作业之一，但我真的不知道该怎么做 . 有人能用简单的英语解释这个问题吗？

arrays algorithm sorting time-complexity binary-search

5 回答

  • 7

    和binary是有序的（lgn），无论如何lgn总是小于n
    这就是你要求考虑排序数组的成本的地方 .

    显然，如果只需要一次搜索，第一种方法比排序数组和二进制搜索更好： n < n*logn + logn . 而且你被问到，第二种方法需要多少次搜索才能变得更有效 .

    暗示结束 .

    回复于
  • 1

    问题是如何决定选择哪种方法 - 只使用线性搜索或排序然后使用二进制搜索 .

    如果你只搜索几次线性搜索更好 - 它是O（n），而排序已经是O（n * logn） . 如果经常搜索同一个集合，则排序更好 - 多次搜索可以变为O（n * n）但排序然后使用二分搜索进行搜索再次是O（n * logn）NumberOfSearches * O（logn）可以更少或者不仅仅是使用线性搜索，具体取决于NumberOfSearches和n的关系 .

    任务是确定NumberOfSearches的确切值（不是确切的数字，而是n的函数），这将使其中一个选项更可取：

    NumberOfSearches * O(n) <> O(n*logn) + NumberOfSearches * O(logn)

    不要忘记每个O（）可以有不同的常量值 .

    回复于
  • 0

    方法的顺序在这里并不重要 . 它告诉你一些问题在问题变得越来越大时算法的扩展程度 . 如果您只知道 O(n) ==它的复杂度随着问题的大小呈线性增长，则无法进行任何精确的计算 . 它不会给你任何数字 .

    对于某些n来说，这很可能意味着具有 O(n) 复杂度的算法比 O(logn) 算法更快 . 因为O（log（n））在变大时会更好地扩展，我们肯定知道有一个 n （问题大小），其中具有O（logn）复杂度的算法更快 . 我们只是不知道什么时候（为了什么 n ） .

    用简单的英语：

    如果你想知道'搜索了多少'，你需要精确的方程来解决，你需要确切的数字 . 搜索顺序需要多少次比较？ （记住n是给定的，所以你可以给出一个数字 . ）用二分搜索进行搜索需要多少次比较（在最坏的情况下！）？在进行二进制搜索之前，必须进行排序 . 让我们添加排序所需的比较次数到二进制搜索的成本 . 现在比较两个数字，哪一个更少？

    二进制搜索速度很快，但排序很慢 . 顺序搜索比二进制搜索慢，但比排序更快 . 但是，无论您搜索多少次，都需要进行一次排序 . 那么，什么时候一个重量级的重量超过每次必须进行慢速（顺序）搜索？

    祝好运！

    回复于
  • 0

    问题是要了解补偿分拣成本所需的数量 NUM_SEARCHES . 所以我们将：

    time( NUM_SEARCHES * O(n) ) > time( NUM_SEARCHES * O(log(n)) + O(n* log(n)) )
    回复于
  • 3

    感谢你们 . 我想我现在明白了 . 你能看看我的答案，看看我是否走在正确的轨道上 .

    对于最坏情况搜索，顺序搜索的比较数为n = 100,000 . 二元搜索的比较数是lg（n）= 17.排序的比较数是（n-1）/ 2 * n =（99999）（50000） . （我正在关注我的课本并使用我班上涵盖的选择排序算法）

    所以让p是最坏情况搜索的数量，然后100,000p>（99999）（50000）17p
    或者p> 50008

    总之，我需要50,008个最坏情况搜索来进行排序和使用二进制搜索比顺序搜索n = 100,000的列表更好 .

    回复于

相关问题