排列函数的时间复杂度
2022-09-03 04:57:18
给定不同数字的集合,返回所有可能的排列。
例如,[1,2,3] 具有以下排列:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
我的迭代解决方案是:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
for(int i=0;i<nums.length;i++)
{
List<List<Integer>> temp = new ArrayList<>();
for(List<Integer> a: result)
{
for(int j=0; j<=a.size();j++)
{
a.add(j,nums[i]);
List<Integer> current = new ArrayList<>(a);
temp.add(current);
a.remove(j);
}
}
result = new ArrayList<>(temp);
}
return result;
}
我的递归解决方案是:
public List<List<Integer>> permuteRec(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) {
return result;
}
makePermutations(nums, result, 0);
return result;
}
void makePermutations(int[] nums, List<List<Integer>> result, int start) {
if (start >= nums.length) {
List<Integer> temp = convertArrayToList(nums);
result.add(temp);
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
makePermutations(nums, result, start + 1);
swap(nums, start, i);
}
}
private ArrayList<Integer> convertArrayToList(int[] num) {
ArrayList<Integer> item = new ArrayList<Integer>();
for (int h = 0; h < num.length; h++) {
item.add(num[h]);
}
return item;
}
根据我的说法,我的迭代解的时间复杂度(big-Oh)是:n * n(n+1)/2~ O(n^3),
我无法计算出递归解的时间复杂度。
谁能解释两者的复杂性?