Постановка задачи: Для заданной строки напишите программу, которая находит все перестановки строки.
Я реализовал это двумя различными способами, и, согласно моему (возможно, ошибочному) анализу сложности времени, второй выполняет меньшие вычисления, но в режиме реального времени первый превосходит второй.
Вопросы:
Является ли мой анализ времени правильным? Почему производительность вычислений отличается?
Какая реализация была бы лучше с точки зрения требований к пространству?
В рекурсивных вызовах я возвращаю неизменные типы данных вместо использования изменяемого аккумулятора (я где-то читал, что это хорошая практика). Является ли это целесообразным, или можно повысить производительность (в пространстве или времени) с помощью изменяемой переменной или статической переменной?
Вместо того, чтобы возвращать List, или было бы лучше обернуть вещи как итератор? Я читал где-то, что может быть лучше, так что вам не нужно хранить все перестановки в памяти сразу, и не нужно предварительно вычислять все перестановки, прежде чем вы начнете что-либо делать с любой из них. Как будет выглядеть код?
- Могу ли я оптимизировать его, используя StringBuffer или StringBuilder вместо Strings? Я думаю, что компилятор автоматически реализует конкатенации при использовании StringBuilder, так это нормально?
- Есть еще какие-нибудь предложения по улучшению кода?
Первая версия:
private static List<String> permuteOne (String partial, String rest) {
List<String> result = new ArrayList<>();
if (rest.length() == 1) {
result.add(partial + rest);
} else {
for (int j = 0; j < rest.length(); j++) {;
result.addAll(permuteOne(partial + rest.charAt(j), rest.substring(0,j) + rest.substring(j+1)));
}
}
return Collections.unmodifiableList(result);
}
Временная сложность T (n) = n * T (n-1)
numOperations (firstVersion) = n + n (n-1) + n (n-1) (n-2) + ... n!
Пространство сложности: ??
Вторая версия:
private static List<String> permuteTwo (String remaining) {
List<String> newList = new ArrayList<>();
if (remaining.length() == 1) {
newList.add(remaining);
} else {
List<String> partialPerms = permuteTwo(remaining.substring(0, remaining.length()-1));
for(String permutation: partialPerms )
for(int j = 0; j <= permutation.length(); j++){
newList.add(permutation.substring(0, j) + remaining.charAt(remaining.length()-1) + permutation.substring(j));
}
}
return newList;
}
Сложность времени T (n) = n! + T (n-1)
numOperations (secondVersion) = 1! + 2! + 3! + ... н!
Космическая сложность: n * n !? <- Не уверен в этом </p>