Biorąc pod uwagę zbiór różnych liczb, zwracaj wszystkie możliwe permutacje.Złożoność czasowa funkcji permutacji
Na przykład, [1,2,3] mają następujące kombinacje:
[[1,2,3], [1,3,2], [2,1,3], [2 , 3,1], [3,1,2], [3,2,1]]
My iteracyjna Solution:
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;
}
My rekurencyjne Solution:
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;
}
Według mnie złożoność czasu (big-Oh) mojego iteracyjnego rozwiązania to: n * n (n + 1)/2 ~ O (n^3)
Nie jestem w stanie określić złożoności czasowej mojego rekursywnego rozwiązanie.
Czy ktoś może wyjaśnić złożoność obu?
Liczba permutacji dla n elementów to n !, więc algorytm do generowania wszystkich n! permutacje miałyby złożoność czasową O (n!). – rcgldr
zarówno dla rekursji, jak i iteracji? – ojas
@OJASJUNEJA tak. Jest to najlepszy możliwy czas uruchamiania tego problemu. Wyobraź sobie, że masz magiczny generator, który wypluwa permutację co 1 sekundę. Nadal trzeba by było poczekać 'n!' Sekund na zakończenie generatora, ponieważ istnieją permutacje 'n!'. – nem035