algorithm - 我什么时候需要使用二进制搜索而不是线性搜索？

Question

需要在一个n-element 表中执行多少次二进制搜索才能买回对表进行排序所需的预处理时间？

Answer 1

这是一个棘手的问题，因为它取决于您用于排序的算法、二进制搜索实现细节等。

在不了解具体实现的情况下，我们只能根据大 O 符号开始分析(但这并不准确，因为算法 O(2n) 的复杂度等于 O(n)，但是大约需要两倍以上)

分析

Binary search = O(logn)
Sorting       = O(nlogn)
Linear search = O(n)

您需要执行 K 次搜索。因此，对于用于不同搜索的原始未排序数组 a[n]

二分查找

1. 排序

2. 搜索 k 次

   总计(BS)= O(logn)+ k * O(logn)

线性搜索

1. 只需搜索 k 次

   总计(LS)= k * O(n)

现在，尝试通过比较 k 和 n 来求解方程式

nlogn + klogn < kn
log(n^n) + log(n^k) < kn
log(n^(n+k)) < kn
n^(n+k) < 2^kn
2^kn - n^(n+k) > 0

(我不是数学家，这是我能得到的最简单的)

现在，当您为算法输入 N 和 K 时，只需计算最后一个表达式，找到最小 K 以通过二分查找取胜.

示例

假设 n = 1000

2^(1000k) - 1000^(1000+k) > 0

当 k > 10 时，此表达式成立， 对于 n = 10000，当 k > 9 时表达式成立

结论

如果数组大于 1000 个元素，则需要执行至少 10 次二进制搜索才能返回排序投资