排列函数的时间复杂度

2022-09-03 04:57:18

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

例如,[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),
我无法计算出递归解的时间复杂度。
谁能解释两者的复杂性?


答案 1

递归解的复杂性为:..O(n!)T(n) = n * T(n-1) + O(1)

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

但是,迭代解不会对 除 以外的任何数字生成正确的排列。3

对于 ,您可以看到 .LHS是(或者更确切地说,从这里开始),RHS是。n = 3n * (n - 1) * (n-2) = n!O(n^3)O(n^n)n=3O(n!)

对于列表大小的较大值,例如,您可以嵌套循环,这将提供有效的排列。在这种情况下,复杂性将是 ,这比 , 或者更确切地说, 要大得多。有一个相当好的关系叫做斯特林近似,它解释了这种关系。nnO(n^n)O(n!)n! < n^n


答案 2

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

借助斯特林近似

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

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

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