置换函数的时间复杂度

给定一组不同的数字,返回所有可能的排列.

例如,[1,2,3]具有以下排列:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3] ,1,2],[3,2,1]]

我的迭代解决方案是:

public List> permute(int[] nums) {
        List> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int i=0;i> temp = new ArrayList<>();
            for(List a: result)
            {
                for(int j=0; j<=a.size();j++)
                {
                    a.add(j,nums[i]);
                    List current = new ArrayList<>(a);
                    temp.add(current);
                    a.remove(j);
                }
            }
            result = new ArrayList<>(temp);
        }
        return result;
    }

我的递归解决方案是:

public List> permuteRec(int[] nums) {
        List> result = new ArrayList>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        makePermutations(nums, result, 0);
        return result;
    }


void makePermutations(int[] nums, List> result, int start) {
    if (start >= nums.length) {
        List 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 convertArrayToList(int[] num) {
        ArrayList item = new ArrayList();
        for (int h = 0; h < num.length; h++) {
            item.add(num[h]);
        }
        return item;
    }

据我所知,迭代解决方案的时间复杂度(大哦)是:n*n(n + 1)/ 2~O(n ^ 3)
我无法弄清楚递归解的时间复杂度.
谁能解释两者的复杂性？

递归解的复杂度O(n!)为，由公式控制T(n) = n * T(n-1) + O(1)。

迭代解决方案具有三个嵌套循环，因此复杂度为O(n^3)。

但是，除了之外，迭代解决方案都不会对任何数字产生正确的排列3。

对于n = 3，您可以看到n * (n - 1) * (n-2) = n!。LHS是O(n^3)（或者O(n^n)从现在n=3开始），RHS是O(n!)。

对于更大的列表大小值，例如n，您可以使用n嵌套循环，这将提供有效的排列。在这种情况下，复杂度将是O(n^n)，并且远大于O(n!)或n! < n^n。有一个很好的关系，称为斯特林近似，可以解释这种关系。