http://netgroup.polito.it/teaching/trc/papers/1998-RangeMatching.pdf 请问一下，有人有读过这篇PAPER吗? 在5.1部分有提到可以运用cascading技巧，使得搜寻时间减为O(ls+log n) 整整读了两个礼拜也研究不出来， 图五的部份paper上提到运用复制技巧，就是将level i+1 复制其point到level i 所以再search level i+1只需花费O(1) 但是照paper那种方法 实在是推不出O(ls+log n) 因为还要再加上ls个O(1) (ls为number of possible prefix lengths) 所以现在我想法是不要用paper的search方法 也不需要运用到复制，观察出在search每个level时 之间有什麽关联性 也就是说search第i+1层时候，或许在search第i层就已经有得到了一些资讯 以致於search时间才会减为(ls+log n) 但是....我真的卡住了，实在是推出不来O(ls+log n) 因为对fractional cascading也不是很清楚，查了一下，有看到一张瀑布的图片 所以是在search的时候Y轴范围会越缩越小吗?可是套用到图5就不会解释了 有前辈能指点一下吗= = 真的快被这篇搞到疯了(最近都有想休学的念头出现= =) 严重怀疑自己是不是不适合读研究所 -- --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 122.118.2.133