java - 置换函数的时间复杂度

Question

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

For example, [1,2,3] have the following permutations:
[ [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;
    }

根据我的说法，我的迭代解决方案的时间复杂度(大哦)是:n * n(n+1)/2~ O(n^3)
我无法计算出我的递归解决方案的时间复杂度。
谁能解释两者的复杂性？

Answer 1

递归解的复杂度为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 .有一个相当不错的关系叫做 Stirling's approximation这解释了这种关系。