перестановки строк Java

Question

Я пишу приложение для Android, в котором у вас есть рекурсивная функция, которая принимает строку и возвращает все перестановки этой строки и всех ее подстрок.Этот подход был трудоемким, особенно с более длинными строками.Я зашел на этот сайт и спросил, есть ли более эффективный способ перестановки строк, и несколько человек предложили дерево Trie.Конечно, Trie был намного быстрее, но я также заметил, что производительность Trie улучшается с более длинными строками.Например, при использовании строки длиной 7 символов Trie работает примерно в 2,5 раза быстрее.Строка из 10 символов Trie примерно в 5 раз быстрее, а строка из 12 символов Trie примерно в 10 раз быстрее.Кто-нибудь знает, почему производительность Trie улучшается с более длинными струнами?

Answer 1

Дело не в том, что производительность Trie улучшается при использовании более длинных строк - конечно, она становится медленнее.Дело в том, что ваше простое решение хуже, чем триан-решение, поэтому оно становится медленнее с более высокой скоростью .

Если бы вы сравнивали три-решение с более эффективным алгоритмом (еслисуществует), тогда вы увидите противоположный эффект.

Вместо этого вы можете измерить производительность каждого алгоритма в режиме «время стены», чтобы увидеть, с какой скоростью каждый алгоритм работает медленнее.Или вы можете проанализировать сами алгоритмы и попытаться выразить их производительность в big-O нотации , что позволит вам легче их сравнивать.