二进制和线性搜索未排序的N个元素 [英] Binary vs Linear searches for unsorted N elements

问题描述

当我们应该使用快速排序时，我试图理解一个公式。例如，我们有一个包含 N = 1_000_000 元素的数组。如果只搜索一次 ，则应该使用简单的线性搜索，但是如果要搜索10次，则应该使用排序数组 O（n log n）。我该如何检测阈值以及何时应该使用输入数组大小以及之后使用二进制搜索的阈值？

I try to understand a formula when we should use quicksort. For instance, we have an array with N = 1_000_000 elements. If we will search only once, we should use a simple linear search, but if we'll do it 10 times we should use sort array O(n log n). How can I detect threshold when and for which size of input array should I use sorting and after that use binary search?

推荐答案

您想要解决可能被形容为粗糙的不平等现象

You want to solve inequality that rougly might be described as

t * n > C * n * log(n) + t * log(n)

其中 t 是检查次数，而 C 是用于排序实现的常数（应通过实验确定）。评估此常数时，可以用数值方法解决不等式（当然有不确定性）

where t is number of checks and C is some constant for sort implementation (should be determined experimentally). When you evaluate this constant, you can solve inequality numerically (with uncertainty, of course)

这篇关于二进制和线性搜索未排序的N个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！