java - 置换 DFS 解决方案的实时复杂度

Question

https://leetcode.com/problems/permutations/ 常见的解决方案是 DFS 递归

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return res;

        DFS(0, nums, res);

        return res;
    }

    private void DFS(int index, int[] nums, List<List<Integer>> res) {
        if (index == nums.length) {
            **//covert nums to list and add to res** o(n)
            return;
        }

        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);
            DFS(index + 1, nums, res);
            swap(nums, index, i);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

从数学中我们可以看到总共有 n! 不同的排列，很多人说 o(n!) 是时间复杂度

但是从代码中我们可以看到递归是 T(n) = O(n)(for add to permutation) + T(n-1) + T(n-2) + ... + T(2) + T( 1）而且我认为 O(n!) 忽略 O(n) 以增加排列我不知道如何从这种重复中概括出一个大 O，任何人都可以帮忙。

非常感谢

标签： javarecursiontime-complexitydepth-first-search