这是G. Michael Scneider和Judith L. Gersting的教科书Invitation to Computer Science]的直接引文。
在3.4.2节的最后,我们讨论了在对未排序列表进行顺序搜索而不是对列表进行排序与使用二进制搜索之间的权衡。如果列表大小为n = 100,000,那么在比较次数方面,第二种方法更好之前必须进行多少次最坏情况的搜索?
我真的没有得到这个问题的要求。
顺序搜索的顺序为(n),二进制的顺序为(lgn),在任何情况下lgn始终小于n。在这种情况下,n已经给出,所以我应该找到什么。
这是我的家庭作业之一,但我真的不知道该怎么办。谁能用简单的英语为我解释这个问题?
[这是教科书邀请函,G。Michael Scneider和Judith L. Gersting的直接引文。在3.4.2节的最后,我们讨论了在使用...
并且二进制数为(lgn),在任何情况下lgn始终小于n
问题是如何决定选择哪种方法-仅使用线性搜索还是先排序然后使用二进制搜索。
方法的顺序在这里并不重要。它告诉您当问题变得越来越大时算法的扩展性如何。如果仅知道O(n)
==,则复杂度在问题的范围内呈线性增长,因此您无法进行任何精确的计算。它不会给你任何数字。
对于顺序搜索,最坏的情况是n = 100000,因此对于p个搜索,需要进行p×100000比较。
问题是关于补偿排序成本所需的数字NUM_SEARCHES
。因此,我们将有:
谢谢你们。我想我现在明白了。您能看看我的答案,看看我是否走对了。