作者netsphere ()
看板Prob_Solve
标题[问题] Suffix tree的时间复杂度?
时间Sun Jul 26 20:36:46 2009
※ [本文转录自 C_and_CPP 看板]
作者: netsphere () 看板: C_and_CPP
标题: [问题] Suffix tree的时间复杂度?
时间: Sun Jul 26 20:35:58 2009
小弟最近在看 ukkonen 的O(n) Suffix tree 演算法
大致上看懂建树的方法了
可是在分析时间复杂度始终看不懂某些地方
最主要的问题是
为什麽canonize()这函数的时间复杂度是O(n)?
实在看不懂作者的解释 Orz
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.22.18.76
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.22.18.76
1F：推 FRAXIS:主要就是Amortize analysis吧 07/27 11:00
2F：→ netsphere:谢谢F大给个方向 07/29 09:36