java 置换函数的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/41627749/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time Complexity of permutation function
提问by ojas
Given a collection of distinct numbers, return all possible permutations.
给定一组不同的数字，返回所有可能的排列。
For example, [1,2,3] have the following permutations:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
例如，[1,2,3] 有以下排列：
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3] ,1,2], [3,2,1] ]
My Iterative Solution is :
我的迭代解决方案是：
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;
}
My Recursive Solution is:
我的递归解决方案是：
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;
}
According to me the time complexity(big-Oh) of my iterative solution is: n * n(n+1)/2~ O(n^3)
I am not able to figure out the time complexity of my recursive solution.
Can anyone explain complexity of both?
根据我的说法，我的迭代解决方案的时间复杂度（大哦）是：n * n(n+1)/2~ O(n^3)
我无法弄清楚我的递归解决方案的时间复杂度。
谁能解释两者的复杂性？
回答by user1952500
The recursive solution has a complexity of O(n!)as it is governed by the equation: T(n) = n * T(n-1) + O(1).
递归解的复杂度为 ，O(n!)因为它由以下方程控制：T(n) = n * T(n-1) + O(1)。
The iterative solution has three nested loops and hence has a complexity of O(n^3).
迭代解决方案具有三个嵌套循环，因此复杂度为O(n^3)。
However, the iterative solution will not produce correct permutations for any number apart from 3.
但是，迭代解决方案不会为除 之外的任何数字生成正确的排列3。
For n = 3, you can see that n * (n - 1) * (n-2) = n!. The LHS is O(n^3)(or rather O(n^n)since n=3here) and the RHS is O(n!).
对于n = 3，你可以看到n * (n - 1) * (n-2) = n!。LHS 是O(n^3)（或者更确切地说是O(n^n)从n=3这里开始）而 RHS 是O(n!)。
For larger values of the size of the list, say n, you could have nnested loops and that will provide valid permutations. The complexity in that case will be O(n^n), and that is much larger than O(n!), or rather, n! < n^n. There is a rather nice relation called Stirling's approximationwhich explains this relation.
对于列表大小的较大值，例如n，您可以有n嵌套循环，这将提供有效的排列。在这种情况下，复杂性将是O(n^n)，并且比 大得多O(n!)，或者更确切地说，n! < n^n。有一个相当不错的关系称为斯特林近似，它解释了这种关系。
回答by Dmitry Bychenko
It's the output(which is huge) matters in this problem, not the routine's implementation. For ndistinct items, there are n!permutations to be returned as the answer, and thus we have at least O(n!)complexity.
它的输出（这是巨大的），在这个问题上，而不是常规的落实事宜。对于n不同的项目，有n!排列作为答案返回，因此我们至少有O(n!)复杂性。
With a help of Stirling's approximation
借助斯特林近似
O(n!) = O(n^(1/2+n)/exp(n)) = O(sqrt(n) * (n/e)^n)
we can easily see, that O(n!) > O(n^c)for anyconstant c, that's why it doesn't matter if the implementation itself adds another O(n^3)since
我们可以很容易地看到，O(n!) > O(n^c)对于任何常量c，这就是为什么实现本身添加另一个并不重要，O(n^3)因为
O(n!) + O(n^3) = O(n!)
