java字符串排列

Question

我正在编写一个Android应用程序,你有一个递归函数,它接受一个字符串并返回该字符串及其所有子字符串的所有排列.这种方法很耗时,特别是对于较长的字符串.我去了这个网站,询问是否有更有效的方法来排列字符串,并且有几个人建议使用Trie树.当然,trie的速度要快得多,但我也注意到Trie的性能随着更长的琴弦而提高.例如,使用7个字符长的字符串,Trie的速度提高了约2.5倍.一条10字符串,Trie的速度快了约5倍,12条字符串的Trie速度提高了约10倍.有谁知道为什么Trie的表现会因为更长的琴弦而变得更好？

Answer 1

这并不是说trie的性能会随着更长的字符串而提高 - 它当然会变得更慢.关键是你的天真解决方案比trie解决方案更糟糕,因此它会以更快的速度变慢.

如果您要将trie解决方案与更高效的算法(如果存在)进行比较,那么您会看到相反的效果.

您可以改为测量每种算法的壁时间性能,以查看每种算法变慢的速率.或者你可以自己分析算法并尝试用big-O表示法表达它们的性能,这样你就可以更容易地比较它们.