圖書館大媽二分稍微升級

04-24

以前看過一個圖書館大媽用二分法的老段子. 人人時代就看到過的東西. 以下來自於學術狀態帝twitter.

圖書館自習的時候,一女生背著一堆書進閱覽室,結果警報響了,大媽讓女生看是哪本書把警報弄響了，女生把書倒出來，一本一本的測。大媽見狀急了，把書分成兩份,第一份過了一下,響了。又把這一份分成兩份接著測，三回就找到了，大媽用鄙視的眼神看著女生，彷彿在說 $O(n)$ 和 $O(log n)$ 都分不清

知乎上看到一些類似的回答. 很多人會提到這個方法有用因為只有一本書. 如果女生有 $k$ 本書可以讓警報響呢? (而且還有人問為什麼不是離開圖書館的時候才要檢測, 這樣可以偷出去幾本書.)

問題可以抽象成給一個n個元素的集合. 有一個子集H. 可以每次檢測一個子集是否包含H中至少一個元素. 用比較少的檢測次數找到H. 我們讓子集H的大小為k. 因為每次檢測我們可以獲得1個bit的結果. 因為有 $nchoose k$ 個不同的可能, 所以我們需要 $log_2 {nchoose k}$ 次檢測.

這裡的log定義為 $max(log n,1)$ .

我們可以給出一個 $O(k log (n/k))$ 次檢測的演算法. 因為前面的下限, 所以這個已經是能達到的最好結果了.

新演算法:

檢測整個集合和H是否相交. 有的話二分, 兩邊都遞歸. 沒有的話停止.

為了簡單起見我們考慮 $n$ 是 $2^d$ 的形式.

我們可以在元素上建立一個complete binary tree. 我們mark一個node, 如果我們檢測了這個node的subtree的所有leaf組成的集合. 我們要做的是考慮如果有k個leaf, 那麼有多少個node被mark. 這個tree的root為 $r$ .

對於給定的k個leaf $L$ , 我們叫一個node為good, 如果對於某一個 $vin L$ , 這個node在 $rv$ path上. 被mark的node的個數最多為2倍good node的個數.

那麼, 最多有多少個good node?

考慮第i層有多少個good node. 第i層也最多有 $2^{i-1}$ 個元素. 而且good node每一層也不能超過k個. 所以我們得知第i層可以有 $min(k, 2^{i-1})$ good nodes. 則我們得到good nodes的數量為 $sum_{i=1}^{1+log n} min(k,2^{i-1}) = O(k(log n - log k)+k) = O(klog (n/k))$ .