Какова временная сложность моего кода?Я проверил это через www.leetcode.com, и это оптимально.Я думаю, что это O (n * n!).Сначала я подумал, что это O (n ^ 2 * n!): Лишние n, так как мы делаем n рекурсивных вызовов.Тем не менее, только первый вызов permute () является доминирующим, а остальные - меньшими, чем n!is >>> (n-1)!
Спасибо заранее!
class Solution {
public List<List<Integer>> permute(int[] nums) {
return permute(nums, nums.length - 1);
}
private List<List<Integer>> permute(int[] nums, int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(n < 0) {
List<Integer> permutation = new ArrayList<Integer>();
result.add(permutation);
return result;
}
// below returns (n-1)! results of size n-1 each
List<List<Integer>> prefixes = permute(nums, n-1);
for(List<Integer> prefix : prefixes) {
List<List<Integer>> permutations = insert(nums[n], prefix);
result.addAll(permutations);
}
return result;
}
// O(n^2) worst case when size of list is n-1
private List<List<Integer>> insert(int num, List<Integer> list) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(int i = 0; i <= list.size(); i++) {
List<Integer> clone = new ArrayList<Integer>();
clone.addAll(list);
clone.add(i, num);
result.add(clone);
}
return result;
}
}