| leetcode46: Permutations 全排列解析及时间复杂度分析 | 您所在的位置：网站首页 › 生成n个数字的全排列算法的时间复杂性为 › leetcode46: Permutations 全排列解析及时间复杂度分析 |
leetcode46: Permutations 全排列解析及时间复杂度分析
|
思路
递归解决问题分3步： 大问题==》小问题 如果我们确定了最后一位数据，那就变成了求解剩下 k−1个数据的排列问题。 而最后一位数据可以是 k 个数据中的任意一个，因此它的取值就有 k 种情况。 所以，“k 个数据的排列”问题，就可以分解成 k 个“n−1个数据的排列”的子问题。 递推公式 比如[1,2,3] perm(1,2,3) = perm(2,3) 1 + perm(1,3) 2 + 3 perm(1,2) 3 终止条件 终止条件 当子数组长度为1的时候 输出当前数组的值 这个递归代码的一个关键的思维节点是：不管递归到哪一层，都是在执行递归函数这同一份代码，不同的层只有一些状态数据不同而已，在本问题中，其状态数据是这个nums数组，这个nums数组是在内存中只有一个，但是在递归过程中，不同的层其状态不同。 代码实现 public class Solution { public List permute(int[] nums) { List res = new ArrayList(); doPermute(nums, nums.length, nums.length, res); return res; } /** * * @param data数组 * @param n data.length * @param k k个 k-1个数据的排列问题 缩小范围 * @param res */ private void doPermute(int[] data, int n, int k, List res) { // 终止条件 当k=1的时候 输出当前数组的值 if (k == 1) { List list = new ArrayList(); // loop invariant: for (int i = 0; i // 将子组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。 // 比如[1,2,3] // perm(1,2,3) = perm(2,3) 1 + perm(1,3) 2 + 3 perm(1,2) 3 // i=0 就是值1 k=3, k-1=2 将0和2交换 之后执行doPermute(k-1) // 内层循环 // i=0 就是值3 k=2, k-1=1 将0和1交换 之后执行doPermute(k-1) 整体相当于执行 perm(2) 3 1 // 之后再把0和1交换回来 3 2 1 // i=1 就是值2 k=2, k-1=1 将1和1交换 之后执行doPermute(k-1) 整体相当于执行 perm(3) 2 1 // 之后再把0和1交换回来 3 2 1 // 回到外层循环 之后再把0和2交换回来 [1,2,3] 整体相当于执行 perm(3,2) 1 // i=1 就是值2 k=3, k-1=2 将1和2交换 之后执行doPermute(k-1) // // 回到外层循环 之后再把1和2交换回来 [1,2,3] 整体相当于执行 perm(1,3) 2 // i=2 就是值3 k=3, k-1=2 将2和2交换 之后执行doPermute(k-1) // // 回到外层循环 之后再把2和2交换回来 [1,2,3] 整体相当于执行 perm(1,2) 3 // 将子组数中的所有的数分别与第一个数交换，这样就总是在处理后k-1个数的全排列 swap(data, i, k - 1); // 这里直接认为下一层返回正确 doPermute(data, n, k - 1, res); // 需要将nums数组复原 swap(data, i, k-1); } } private void swap(int[] data, int i, int j){ int temp = data[i]; data[i] = data[j]; data[j] = temp; } } 时间复杂度分析采用递归树的方式 第二层有 n 个节点，每个节点分解需要 n−1 次交换，所以第二层总的交换次数是 n∗(n−1)。 第三层有 n∗(n−1) 个节点，每个节点分解需要 n−2 次交换，所以第三层总的交换次数是 n∗(n−1)∗(n−2)。 以此类推，第 k 层总的交换次数就是 n∗(n−1)∗(n−2)∗…∗(n−k+1)。 最后一层的交换次数就是 n∗(n−1)∗(n−2)∗…∗2∗1。每一层的交换次数之和就是总的交换次数。 这个公式的求和比较复杂，我们看最后一个数，n∗(n−1)∗(n−2)∗…∗2∗1 等于 n!，而前面的 n−1 个数都小于最后一个数，所以，总和肯定小于 n∗n!，也就是说，全排列的递归算法的时间复杂度大于 O(n!)，小于 O(n∗n!)，虽然我们没法知道非常精确的时间复杂度，但是这样一个范围已经让我们知道，全排列的时间复杂度是非常高的。 |
第一层分解有 n 次交换操作，【本文地址】