[問題] Suffix tree的時間複雜度?

[netsphere ()]

※ [本文轉錄自 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
推 FRAXIS:主要就是Amortize analysis吧
→ netsphere:謝謝F大給個方向