字符串排列递归代码的时间复杂度分析疑问（CTCI第六章例12）

先贴出讨论的递归代码：

public static void permutation(String str) { permutation(str, ""); }
public static void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

你的三个疑问逐一解答： #

1. 时间复杂度到底是O(n²n!)还是O(n³n!)？字符串拼接O(n)的原因？ #

首先纠正你的误解：你的O(n³n!)结论是错误的，书中给出的O(n²n!)是一个宽松的上界，而更精确的复杂度其实是O(n*n!)。

先解释字符串拼接为什么是O(n)级别的：
Java中的String是不可变的，每次拼接都会创建新字符串并复制所有参与拼接的字符。对于当前递归调用中str长度为m的情况：

• rem = str.substring(0,i) + str.substring(i+1)：两个子串总长度是m-1，拼接需要复制m-1个字符，时间O(m)；
• prefix + str.charAt(i)：prefix长度是n-m，加上1个字符后总长度n-m+1，拼接需要复制n-m+1个字符，时间O(n-m+1)。
  两者加起来的总时间是O(m + (n-m+1)) = O(n)，和当前m的大小无关，所以每次循环迭代里的字符串操作时间都是O(n)。

接下来看总工作量：递归树的总循环迭代次数是n + n*(n-1) + n*(n-1)*(n-2) + ... + n!，这个求和式可以变形为n! * (1/(n-1)! + 1/(n-2)! + ... + 1/0!)，而括号里的部分是自然常数e的近似（约等于2.718），所以总迭代次数是O(n!)。乘以每次迭代的O(n)操作时间，总时间就是O(nn!)。书中给出的O(n²n!)是一个更保守的上界（因为可以把括号里的和粗暴地放大到n），但精确复杂度是O(n*n!)。

2. 如何理解“总迭代次数与递归树节点数相近，每个节点平均迭代次数为常数”？ #

先明确两个概念：

• 递归树节点数：包括所有递归调用（从初始调用到叶子节点），总数是1 + n + n*(n-1) + ... + n!，同样可以近似为e*n!；
• 总迭代次数：就是所有非叶子节点的for循环执行次数之和，也就是上面提到的n + n*(n-1) + ... + n!，同样近似为e*n!。

两者都是O(n!)量级，所以说“总迭代次数与递归树节点数相近”。而平均每个节点的迭代次数 = 总迭代次数 / 节点总数 ≈ en! / en! = 1，是个常数，这就是这句话的含义。

3. 你的求和分析方法是否有效？结果是否为O(n*n!)？ #

你的求和思路是有效的，最终结果确实是O(n*n!)。

你的计算逻辑：

• 第1层（初始调用）：1个节点，循环n次，总工作量n*n（n次迭代 × 每次O(n)操作）；
• 第2层：n个节点，每个循环n-1次，总工作量n*(n-1)*n；
• ...
• 第k层：n!/(n-(k-1))!个节点，每个循环n-(k-1)次，总工作量n!/(n-(k-1))! * (n-(k-1)) *n；

把所有层的工作量加起来，总和是n*(n + n*(n-1) + n*(n-1)*(n-2) + ... +n!)，而括号里的部分是O(n!)，所以总和就是O(n*n!)，和我们之前的结论一致。这个方法通过分层计算工作量，逻辑是通顺的，是分析递归时间复杂度的常用思路之一。

内容的提问来源于stack exchange，提问作者EnriqueC