排列算法的复杂性分析

Question

我正在尝试了解用于生成数组排列的算法的时间和 space 复杂性。给定部分构建的排列，其中 n 元素中的 k 已经 selected，算法 selects 元素 k+1 来自剩余的 n-k元素并调用自身 select 剩余的 n-k-1 个元素：

public static List<List<Integer>> permutations(List<Integer> A) {
    List<List<Integer>> result = new ArrayList<>();
    permutations(A, 0, result);
    return result;
  }

  public static void permutations(List<Integer> A, int start, List<List<Integer>> result) {
    if(A.size()-1==start) {
      result.add(new ArrayList<>(A));
      return;
    }

    for (int i=start; i<A.size(); i++) {
      Collections.swap(A, start, i);
      permutations(A, start+1, result);
      Collections.swap(A, start, i);
    }
  }

我的想法是，在每次调用中我们交换集合的元素 2n 次，其中 n 是要排列的元素数，并进行 n 次递归调用。所以运行时间似乎符合递归关系 T(n)=nT(n-1)+n=n[(n-1)T(n-2)+(n-1)]+n=...=n+n(n-1)+n(n-1)(n-2)+...+n!=n![1/(n-1)!+1/(n-2)!+...+1]=n!e，因此时间复杂度为 O(n!)，space 复杂度为 O(max(n!, n))，其中 n!是排列总数，n是递归树的高度。

这个问题取自《编程面试基础》一书，他们说时间复杂度是 O(n*n!) 因为“函数调用的次数 C(n)=1+nC(n-1) ... [这解决了到] O(n!) ... [和] ... 我们在递归调用之外的每个调用中进行 O(n) 计算。

哪个时间复杂度是正确的？

Answer 1

该算法的时间复杂度，按执行的基本操作数计算，为Θ(n * n!)。考虑一下算法终止时 result 列表的大小——它包含 n! 个排列，每个排列的长度为 n，我们不能创建一个总元素为 n * n! 的列表在不到那个时间。 space 复杂度是相同的，因为递归堆栈一次只有 O(n) 个调用，所以输出列表的大小决定了 space 复杂度。

如果仅计算对 permutations() 的递归调用次数，则该函数被调用 O(n!) 次，尽管这通常不是 'time complexity' 的含义，没有进一步说明。换句话说，你可以在O(n!)时间内生成所有的排列，只要你不在生成后读取或写入这些排列。

你对运行-time 的推导失败的部分在 T(n) 的定义中。如果将 T(n) 定义为 'the run-time of permutations(A, start) when the input, A, has length n'，则不能根据 T(n-1) 或 T() 的任何其他函数递归定义它，因为所有递归调用中输入的长度是n,A的长度

一种更有用的定义 T(n) 的方法是将其指定为 permutations(A', start) 的运行时间，当 A' 是 固定的任何排列时，初始数组 A 和 A.length - 开始 == n。这里的递推关系很容易写出来：

T(x) = x * T(x-1) + O(x)     if x > 1
T(1) = A.length

这考虑到最后一个递归调用 T(1) 必须执行 O(A.length) 工作以将该数组复制到输出，并且这个新的递归给出了教科书中的结果。

排列算法的复杂性分析

Complexity analysis for the permutations algorithm

algorithm

recursion

time-complexity

computer-science

space-complexity