[問題] Suffix tree的時間複雜度?
看板Prob_Solve (計算數學 Problem Solving)作者netsphere時間15年前 (2009/07/26 20:36)推噓1(1推 0噓 1→)留言2則, 2人參與討論串1/1
※ [本文轉錄自 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
推
07/27 11:00, , 1F
07/27 11:00, 1F
→
07/29 09:36, , 2F
07/29 09:36, 2F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
