排列问题算法复杂度以及java版本实现的复杂度问题

Question

老师您好，看完8-3节排列问题，我有两个疑问：

1. 排列问题的算法时间复杂度是否是 O(n!)？其中n为原数组中元素个数。
2. 在java版本实现代码（参见您的代码仓库中，每次找到了一个排列，添加进结果的时候，需要拷贝整个排列:
   res.add((LinkedList<Integer>)p.clone());
   我自己的实现是使用：
   res.add(new LinkedList<>(p));
   实现同样的功能，但是这就带来了每一个可能解都有一个额外的 O(n) 时间复杂度。所以此时的java版本实现是否时间复杂度为 O(n * n!)？如果是的话有没有什么办法可以避免这个时间开销？

谢谢。

Answer 1

慕工程4033812 2019-07-23 06:59:20

请老师和大佬指点一下 为什么p.clone 没有额外时间复杂度 而new LinkedList<>(p)有额外的 O(n) 时间复杂度？

Answer 2

liuyubobobo 2019-02-03 09:59:34

赞问题！

首先，是的，时间复杂度是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)其实是不一样的，在不严谨的复杂度分析中，我们都说他是指数复杂度：）类似的还有多项式复杂度，对数复杂度，等等：）

继续加油！：）

• 幕布斯1098637 #1

  老师，为什么我们找到一个可以添加的p了，要克隆一下或者new一个一模一样的list添加进去呢？后面对p的改变也会影响到res的数据吗？我试了一下不new或者clone的话，res里面得到的全是空数组，我用的是java

• liuyubobobo 回复 幕布斯1098637 #2

  是的，会改变，因为java中所有的对象都是引用：）

• 慕工程4033812 回复 幕布斯1098637 #3

  是shallow copy 浅拷贝的原因吧