Sai*_*ahi 4 arrays sorting algorithm binary-search time-complexity
这是G. Michael Scneider和Judith L. Gersting 的教科书" 计算机科学邀请"的直接引用.
在3.4.2节的最后,我们讨论了在未排序列表上使用顺序搜索而不是对列表进行排序然后使用二进制搜索之间的权衡.如果列表大小是n = 100,000,那么在第二种替代方案在比较次数方面更好之前必须进行多少次最坏情况搜索？
我真的没有得到问题的要求.
顺序搜索是有序(n),二进制有序(lgn),无论如何lgn总是小于n.在这种情况下,已经给出了n,所以我应该找到什么.
这是我的家庭作业之一,但我真的不知道该怎么做.有人能用简单的英语解释这个问题吗？
和二进制是有序的(lgn),无论如何lgn总是小于n
这是你错的地方.在分配中,您还需要考虑排序数组的成本.
显然,如果你只需要一次搜索,第一种方法比排序数组和二进制搜索更好:n < n*logn + logn.而且你被问到,为了提高效率,你需要多少次搜索才能获得第二种方法.
暗示结束.