a*u
发帖数: 97 | 1 给一个string建立suffix array，然后sort这些substrings，复杂度是多少？O(nlgn)
or O(n^2lgn)?
比如 String "bananna", size n = 7
suffix array
{
banana
anana
nana
ana
na
a
}
after sorting
{
a
ana
anana
banana
na
nana
}
for a string size n, creating the suffix array is O(n), sorting is supposed
to be O(nlgn), but I somehow feel it is O(n^2lgn), since the comparison
between two substrings are O(n).
Where did I miss? | a*u
发帖数: 97 | 2 又查了下，brute force就是n^2lgn, 但是现在有improved O（nlgn）算法，也有exact
bound n的算法了。恩
)
【在 a*u 的大作中提到】
: 给一个string建立suffix array，然后sort这些substrings，复杂度是多少？O(nlgn)
: or O(n^2lgn)?
: 比如 String "bananna", size n = 7
: suffix array
: {
: banana
: anana
: nana
: ana
: na
| s******t
发帖数: 2374 | 3 你这个问题是不是programming pearls的题目？ | a*u
发帖数: 97 | 4 是的啊，somewhat真是大牛，通读熟记了。
那里面讲是nlgn sort those suffix strings, 我看的应该是在O（n）出现之前的版本
。 |
|
