排列问题算法复杂度以及java版本实现的复杂度问题
来源：8-3 排列问题 Permutations
玉涵
2019-02-02
老师您好，看完8-3节排列问题，我有两个疑问：
- 排列问题的算法时间复杂度是否是 O(n!)？其中n为原数组中元素个数。
- 在java版本实现代码（参见您的代码仓库中，每次找到了一个排列，添加进结果的时候，需要拷贝整个排列:
res.add((LinkedList<Integer>)p.clone());
我自己的实现是使用：res.add(new LinkedList<>(p));
实现同样的功能，但是这就带来了每一个可能解都有一个额外的 O(n) 时间复杂度。所以此时的java版本实现是否时间复杂度为 O(n * n!)？如果是的话有没有什么办法可以避免这个时间开销？
谢谢。
写回答
2回答
-
慕工程4033812
2019-07-23
请老师和大佬指点一下 为什么p.clone 没有额外时间复杂度 而new LinkedList<>(p)有额外的 O(n) 时间复杂度？
00 -
liuyubobobo
2019-02-03
赞问题！
首先，是的，时间复杂度是O(n*n!)。并且不可能避免这个时间开销。因为算法要求输出所有的排列。n个元素的所有排列一共是n!个序列，每个序列包含n个元素。所以问题的输出就包含n*n!个元素，至少需要这么多时间才能得到这个输出：）
另一方面，从复杂度分析的角度，O(n*n!)和O(n!)确实不一样，但是整体而言，他们都是“阶乘级别的复杂度”。这是因为O(n*n!) <= O((n + 1) * n!) = O((n + 1)!)，换句话说，我们可以找到一个O(n*n!)的另外一个上界，就是O((n+1)!)，他还是阶乘的形式，只是是多少的阶乘有变化。（n还是n+1）在不严谨的复杂度分析中，我们都说他们是阶乘复杂度。同理，O(2^n)和O(3^n)其实是不一样的，在不严谨的复杂度分析中，我们都说他是指数复杂度：）类似的还有多项式复杂度，对数复杂度，等等：）
继续加油！：）
032019-07-23
相似问题