《编程珠玑》习题2.6(9)顺序搜索和二分搜索的的代价

9.顺序搜索和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序索消耗的预处理时间？

 

假设我们排序使用快排，则复杂度约为O(n*logn).

顺序查找无序序列的复杂度为O(n). 二分法为O(log2(n)).

n*logn = n*x - log2（n）;

当n偏大时， 基本相对于n*x, log2（n）值可以忽略.例如n的1024时， log2 (n)仅为10。

所以等式划为 n*logn = n*x

 

大概执行logn次即可弥补预处理索消耗的时间。