排列函数的时间复杂度

Question

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

例如，[1,2,3] 具有以下排列：
[ [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;
    }

根据我的说法，我的迭代解决方案的时间复杂度（big-Oh）是：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要大得多。有一个相当不错的关系叫做斯特林近似，它解释了这种关系。

Answer 2

在这个问题中，输出（这是巨大的）很重要，而不是例程的实现。对于n不同的项目，需要返回n!排列作为答案，因此我们至少具有O(n!)的复杂性。

借助斯特林近似

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

我们可以很容易地看到，对于任何常量c O(n!) > O(n^c)，这就是为什么实现本身是否添加另一个O(n^3)并不重要，因为

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

Answer 3

就调用方法makePermutations的次数而言，确切的时间复杂度为：

O( 1 + n + n(n-1) + n(n-1)(n-2) + ... )

当 n = 3 时：

O( 1 + 3 + (3*2) + (3*2*1) ) = O(16)

这意味着，对于 n = 3，方法makePermutations将被调用 16 次。

Answer 4

我认为最优排列函数的空间复杂度将是 O（n * n！），因为有 n！ 要返回的数组总数，每个数组的大小均为 n。