Cho một tập hợp các số riêng biệt, trả về tất cả các hoán vị có thể.Độ phức tạp theo thời gian của hàm hoán vị
Ví dụ, [1,2,3] có hoán vị sau:
[[1,2,3], [1,3,2], [2,1,3], [2 , 3,1], [3,1,2], [3,2,1]]
giải pháp lặp của tôi là:
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;
}
giải pháp đệ quy của tôi là:
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;
}
Theo tôi độ phức tạp thời gian (lớn-Oh) của giải pháp lặp của tôi là: n * n (n + 1)/2 ~ O (n^3)
Tôi không thể tìm ra độ phức tạp của đệ quy dung dịch.
Bất cứ ai có thể giải thích sự phức tạp của cả hai?
Số hoán vị cho các phần tử n là n !, do đó, một thuật toán để tạo tất cả n! hoán vị sẽ có độ phức tạp thời gian O (n!). – rcgldr
cho cả đệ quy và lặp lại? – ojas
@OJASJUNEJA có. Đây là thời gian chạy tốt nhất có thể hình dung được cho vấn đề này. Hãy tưởng tượng nếu bạn có một máy phát điện ma thuật mà chỉ phun ra một hoán vị mỗi 1 giây. Bạn vẫn cần phải đợi 'n!' Giây để máy phát điện này kết thúc vì có hoán vị 'n!'. – nem035