作者yoco315 (眠月)
看板CSSE
标题[讨论] 建构 suffix tree 的速度？
时间Sat Mar 18 01:46:51 2006
suffix tree 用暴力法建构需要 O(n^2)，
教授上课教了利用 suffix link 的 O(n) 的建置方法，
我实作出来以後发现速度好像没快多少，
後来在程式码当中加上了一些程式码来统计 "比较" 的次数
发现使用了 suffix link 以後也只不过减少了一成左右的比较数
（alphabet = 4, string length = 10000）
也就是说时间变成原来的 0.9 倍，实在没什麽帮助..
请问是我写错，还是 suffix tree 的助益本来就不大？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.129.180
1F：推 littleshan:你应该测试更大的 input 并比较它们的成长速度 03/18 02:34
2F：推 H45:你应该看输入和时间的成长关系 03/19 09:34
3F：→ yoco315:我发现是我实作上少了一个可以跳过一些比较的动作 03/19 11:26