Question

如果列表有1024个项(lg1024 = 10)，排序列表并使用二进制搜索的收益点是什么(搜索次数是多少)? 如果列表有2048个项，您的答案会如何改变? 而不是使用顺序搜索。如果列表有1024个项(lg1024 = 10)，排序列表并使用二进制搜索的收益点在搜索第11个元素时到达。如果列表有2048个项目(lg2048 = 11)，则预计在第12个搜索之后通过排序列表和使用二进制搜索来获得回报。

Answer 1

“线性查找”曲线和“二分查找”曲线相交的位置取决于访问/插入单个项需要多长时间以及有多少项。这对于每个组合的编译器、内存和CPU架构、列表中数据/节点的类型、数据值的分布、使用的排序和插入算法等都是不同的......但是，随着“足够大”的项集，尽管“大O”界限可能不精确地描述任何特定运行，它的运行时间可以通过提到它的上限如何随着增加的项数而增长来描述。

如果您能了解您要插入或搜索的具体算法，并确定组成列表访问的实际指令，以及找出执行它们所需的时钟周期等等，那么您可以精确地计算出这些。

然后，您可以确定哪个更快，以及在哪个时间点。如果您知道数据值，您可以对其进行建模。但是如果您不知道，您必须假设（例如，如果您插入的数据值已经排序，那么它会如何影响您的排序或插入函数？）

例如，单个项目检索可能需要1微秒。比较两个项目可能需要0.5微秒。将具有100个项目的排序列表插入到列表中可能需要X次检索，Y次比较和Z次更新/写入......而无序列表可能需要更多或更少取决于已有的内容以及要插入的内容。

Answer 2

如果列表未排序，则需要O（n）的时间来找到它。使用快速排序进行排序的成本为O（n*log n），然后使用二分查找是O（log n）。假设x是搜索次数。 x * n = x * logn + n * logn 。通过放入不同的值，您可以估计动态。我的粗略估计表明，如果n = 1024且搜索次数大于~10，则最好先对其进行排序。将1024放入n中并尝试。

友情链接