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