[算法]请帮忙看看我的分析对不对（关键词：二分查找，缓冲）

herberteuler

众所周知，对于已排序好的数据，二分查找的时间效率是 O(log n)，其中 n 是数据的数量。

现在，假设要进行许多次二分查找，并加入一个缓冲，它保存了上一次查找的元素。查找时，被查数据先与缓冲元素比较，并在由这次结果得到的子序列中查找。我想知道这样查找的时间效率。

仍然假设数据数量为 n，并且缓冲元素的位置在第 0 至 n-1 个位置的概率是相等的，被查数据的值大于、等于、或小于缓冲元素的概率也是相等的。这样，如果缓冲元素位于位置 m，则期望的查找次数为 1/3 + (log m)/3 + (log(n-m))/3，一次查找的期望次数为

1/n * sum_{m=0}^{n-1}[ 1/3 + (log m)/3 + (log(n-m))/3 ]

暂时不作继续的分析，到这里为止，我的分析正确吗？

soloforce

被查数据的值大于、等于、或小于缓冲元素的概率也是相等的。

这个假设很牵强。

但这个假设成立的话，应该是如此计算的

soloforce

不过楼主这个带缓冲的搜索的确是个好主意，根据局部性原理，应该会改善搜索性能。
如果改用2个缓冲，或许更有趣

yuhch123

Post by herberteuler

仍然假设数据数量为 n，并且缓冲元素的位置在第 0 至 n-1 个位置的概率是相等的，被查数据的值大于、等于、或小于缓冲元素的概率也是相等的。

应该不相等的吧。。。等于的概率是1/n，剩下的2个是(n-1)/2n

herberteuler

呵呵，我也想到了。这样，期望的次数就是

1.   S
   
2. = (n-1)/2n^2 * sum_{i=1}^n [ log i + log(n-i) ] + 1 / n
   
3. = (n-1)/n^2 * sum_1^n [ log i ] + 1 / n
   
4. = (n-1)/n * log{ [ prod_1^n (i) ] ^ {1/n}} + 1 / n

复制代码

最粗略的估计是

1. S < (n-1)/n * log n + 1 / n
   
2.   ~ log n ( n -> +infinite)

复制代码

但这样太粗略了。那位能帮忙给个更精细一些的估计呀？谢谢。

herberteuler

Post by Lolita
不过楼主这个带缓冲的搜索的确是个好主意，根据局部性原理，应该会改善搜索性能。
如果改用2个缓冲，或许更有趣

我想我还是先把目前能做的做好再继续吧。更一般的情况是，在整个序列中，某些区间中的元素被频繁查询。这种情况里，到底选几个作为缓冲似乎和这种区间的个数有关。无奈，我对最简单的情况的理解还不够，无法继续。

Iambitious

对于这种应用，可以考虑用hash table来进行查找，会大大降低时间复杂度，还有就是cache对于二分查找是没有意义的。你的概率计算的不正确，对于n个数，另取一个数与n个数相等的概率为n/(你所能取所有数)，对于一般的数任意的情况，此种概率几乎为0，而同样与n个数不相等的概率近似为1，所以搜索一次的时间复杂度为log(m*(n-m))/2,当m处于n个数的中间时，与正常的二分查找复杂度相同，否则要比原来的效率低。
以上的阐述都是建立在数据之间是独立无关的情况下，如果符合某种统计规律则不在成立。

herberteuler

Post by Iambitious
对于这种应用，可以考虑用hash table来进行查找，会大大降低时间复杂度，还有就是cache对于二分查找是没有意义的。你的概率计算的不正确，对于n个数，另取一个数与n个数相等的概率为n/(你所能取所有数)，对于一般的数任意的情况，此种概率几乎为0，而同样与n个数不相等的概率近似为1，所以搜索一次的时间复杂度为log(m*(n-m))/2,当m处于n个数的中间时，与正常的二分查找复杂度相同，否则要比原来的效率低。
以上的阐述都是建立在数据之间是独立无关的情况下，如果符合某种统计规律则不在成立。

分析得有道理。谢谢。顺便问一下，上面的式子 S，如果要估计的话，是不是这样：

1.   S
   
2. = (n-1)/n^2 * sum_1^n log(i/n) + (n-1)/n log n + 1 / n
   
3. ~ (n-1)/n * int_0^1 log x dx + (n-1)/n * log n + 1 / n
   
4. ~ 2/n - 1 + (n-1)/n * log n

复制代码

Iambitious

对不起，你写的式子，我看不明白，能写的清楚一些吗？

soloforce

Post by Iambitious
对不起，你写的式子，我看不明白，能写的清楚一些吗？

这是tex版的公式 ：）