请求分析生成字母全排列的递归Java代码的时间复杂度

这段Java代码通过递归方式生成输入字符串的所有全排列，比如输入abc会输出6种排列组合。下面详细分析它的时间复杂度：

核心递归逻辑拆解 #

递归函数scrambleLetters的执行逻辑分为两部分：

• 基准情况：当剩余字符为空时，打印当前已拼接的排列结果
• 递归情况：遍历剩余字符的每个位置，将该字符移到已拼接字符串中，递归处理剩余字符，之后回溯恢复初始状态

时间复杂度推导 #

1. 递归调用次数 #

对于长度为n的输入字符串，全排列的总数是n!（n的阶乘）。但递归树的节点数不止n!，每个节点对应一次递归调用，节点总数为：
n + n*(n-1) + n*(n-1)*(n-2) + ... + n!
这个求和式的主导项是n!，因此递归调用的总次数是O(n!)。

2. 每个递归节点的操作耗时 #

代码中每次递归循环里的字符串操作（removeFromIndex、insertAtIndex、字符串拼接）基于Java不可变String实现，这些操作需要复制字符，时间复杂度为O(k)，其中k是当前操作的字符串长度（剩余字符或已拼接字符串的长度）。

3. 总时间复杂度计算 #

将每个递归层次的耗时相加：
对于剩余字符长度为k的层次，共有n!/(n-k)!个节点，每个节点耗时O(k)，总耗时为：
sum_{k=1到n} [k * n!/(n-k)!]

通过数学变换推导：
令m = k-1，求和式可转换为n * sum_{m=0到n-1} (n-1)!/( (n-1)-m )!
而sum_{m=0到n-1} (n-1)!/( (n-1)-m )!是(n-1)!乘以自然常数e的泰勒展开前n项（结果小于e，约2.718），因此总和为n! * e，属于**O(n!)**的时间复杂度。

为什么不是O(2^n) #

你之前误以为是O(2^n)，大概率是混淆了子集生成和全排列生成的时间复杂度：

• 子集生成的总数是2^n，时间复杂度为O(n*2^n)
• 全排列的总数是n!，阶乘增长速度远快于指数增长（比如n=10时，2^10=1024，10!=3628800），两者不在同一量级。

中文注释版代码 #

import java.util.Scanner;

public class WordScrambler {

    // 递归生成全排列
    // remainLetters: 剩余未使用的字母
    // scramLetters: 已拼接的排列结果
    public static void scrambleLetters(String remainLetters, String scramLetters) {
        String tmpString;      // 临时存储单个字符
        int i;                 // 循环索引

        // 基准情况：所有字母都已使用，打印当前排列
        if (remainLetters.length() == 0) {
            System.out.println(scramLetters);
        } else {
            // 递归情况：将剩余字母中的每个字符依次加入已拼接结果，递归后回溯
            for (i = 0; i < remainLetters.length(); ++i) {
                // 将当前字符移到已拼接结果中
                tmpString = remainLetters.substring(i, i + 1);
                remainLetters = removeFromIndex(remainLetters, i);
                scramLetters = scramLetters + tmpString;

                // 递归处理剩余字母
                scrambleLetters(remainLetters, scramLetters);

                // 回溯：将字符放回剩余字母，恢复已拼接结果
                remainLetters = insertAtIndex(remainLetters, tmpString, i);
                scramLetters = removeFromIndex(scramLetters, scramLetters.length() - 1);
            }
        }
    }

    // 删除指定位置的字符，返回新字符串
    public static String removeFromIndex(String origStr, int remLoc) {
        String finalStr;
        // 复制指定位置前的字符 + 指定位置后的字符
        finalStr = origStr.substring(0, remLoc);
        finalStr += origStr.substring(remLoc + 1, origStr.length());
        return finalStr;
    }

    // 在指定位置插入字符，返回新字符串
    public static String insertAtIndex(String origStr, String insertStr, int addLoc) {
        String finalStr;
        // 复制指定位置前的字符 + 插入字符 + 指定位置后的字符
        finalStr = origStr.substring(0, addLoc);
        finalStr += insertStr;
        finalStr += origStr.substring(addLoc);
        return finalStr;
    }

    public static void main(String[] args) {
        Scanner scnr = new Scanner(System.in);
        String wordScramble;      // 用户输入的待排列单词

        // 提示用户输入
        System.out.print("请输入要生成全排列的单词：");
        wordScramble = scnr.next();

        // 调用递归方法
        scrambleLetters(wordScramble, "");
        // 注：原代码中的wordcounter未定义，需补充定义后才能正常输出该语句
        // System.out.println("counter " + wordcounter);
    }
}

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