推 littleshan:你應該測試更大的 input 並比較它們的成長速度 03/18 02:34
推 H45:你應該看輸入和時間的成長關係 03/19 09:34
→ yoco315:我發現是我實作上少了一個可以跳過一些比較的動作 03/19 11:26
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