时间对于我的解决方案包含不同数量的整数数组的所有排列复杂

Question

什么是我的代码的时间复杂度？我跑这个通过www.leetcode.com，它是最佳的。我认为它的O（N * N！）。首先，我认为这是为O（n ^ 2 * N！）：额外ñ，因为我们做n次递归调用。但是，只有在第一次调用置换（）是显性的，而那种相形见绌休息，因为N！为>>>（N-1）！

由于前期！

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        return permute(nums, nums.length - 1);
    }

    private List<List<Integer>> permute(int[] nums, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(n < 0) {
            List<Integer> permutation = new ArrayList<Integer>();
            result.add(permutation);
            return result;
        }

        // below returns (n-1)! results of size n-1 each
        List<List<Integer>> prefixes = permute(nums, n-1); 
        for(List<Integer> prefix : prefixes) {
            List<List<Integer>> permutations = insert(nums[n], prefix);
            result.addAll(permutations);
        }
        return result;
    }

    // O(n^2) worst case when size of list is n-1
    private List<List<Integer>> insert(int num, List<Integer> list) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(int i = 0; i <= list.size(); i++) {
            List<Integer> clone = new ArrayList<Integer>();
            clone.addAll(list);
            clone.add(i, num);
            result.add(clone);
        }
        return result;
    }

}

Answer 1

我认为这个问题可能更适合于https://codereview.stackexchange.com/