Złożoność czasowa funkcji permutacji

Question

Biorąc pod uwagę zbiór różnych liczb, zwracaj wszystkie możliwe permutacje.

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?

Answer 1

Rozwiązanie rekursywne ma złożoność O(n!), ponieważ jest regulowane przez równanie: T(n) = n * T(n-1) + O(1).

Rozwiązanie iteracyjne ma trzy zagnieżdżone pętle, a zatem ma złożoność O(n^3).

Jednak iteracyjne rozwiązanie nie spowoduje poprawnych permutacji dla dowolnej liczby oprócz 3.

Dla n = 3 widać, że n * (n - 1) * (n-2) = n!. LHS to O(n^3) (lub raczej O(n^n) od n=3), a RHS to O(n!).

Dla większych wartości o wielkości listy, powiedzmy n, możesz mieć zagnieżdżone pętle n, które zapewnią poprawne permutacje. W tym przypadku złożoność będzie wynosić O(n^n) i jest znacznie większa niż O(n!), a raczej n! < n^n. Istnieje relatywnie dobra relacja o nazwie Stirling's approximation, która wyjaśnia tę relację.

Answer 2

Wyjście wyjściowe (co jest ogromne) ma znaczenie w tym problemie, a nie implementacja rutyny. W przypadku różnych elementów, n, jako odpowiedź są zwracane permutacje n!, a więc mamy złożoność co najmniej O(n!).

Z pomocą Stirling's approximation

O(n!) = O(n^(1/2+n)/exp(n)) = O(sqrt(n) * (n/e)^n) 

możemy łatwo zobaczyć, że O(n!) > O(n^c) dla dowolny stała c, to dlaczego nie ma znaczenia, jeśli sama realizacja dodaje inny O(n^3) od

O(n!) + O(n^3) = O(n!)