我正在编写一个 Android 应用程序，其中有一个递归函数，它接受一个字符串并返回该字符串及其所有子字符串的所有排列。这种方法非常耗时，尤其是对于较长的字符串。我访问了这个站点并询问是否有更有效的方法来排列字符串，有几个人建议使用 Trie 树。当然，trie 的速度更快，但我还注意到，Trie 的性能随着字符串的增加而提高。例如，使用 7 个字符长的字符串，Trie 大约快 2.5 倍。一个 10 个字符的字符串 Trie 大约快 5 倍，而一个 12 个字符的字符串 Trie 大约快 10 倍。有谁知道为什么 Trie 的性能在字符串越长的情况下越好？
最佳答案
并不是 trie 的性能随着字符串的增加而提高——它当然会变慢。关键是您的原始解决方案比 trie 解决方案更糟糕，因此它以更快的速度变得更慢。
如果您将 trie 解决方案与更高效的算法(如果存在)进行比较，那么您会看到相反的效果。
您可以改为测量每种算法的挂钟性能，以查看每种算法变慢的速度。或者您可以分析算法本身并尝试在 big-O notation 中表达它们的性能这样您就可以更轻松地比较它们。
关于Java字符串排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9243823/