字符串排列时间复杂度疑问：为何是O(n²·n!)而非O(n·n!)

我正在阅读Gayle Laakmann McDowell所著的《Cracking the Coding Interview》，对书中时间复杂度章节第51页的例12存在疑问。该例给出一段生成字符串全排列的代码，书中标注其时间复杂度为O(n²·n!)，但我难以理解其中逻辑。

代码示例 #

void permutation(String str) {
    permutation(str, "");
}

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));
        }
    }
}

我的推导逻辑 #

我自行推导的时间复杂度为O(n·n!)，推导过程如下：以初始调用permutation("hello", "")为例，第一层循环有5次迭代，每个迭代触发递归调用；后续每层递归的循环次数依次为4、3、2、1，总共有n!次permutation()调用，每次调用耗时O(n)，因此得出O(n·n!)。

请指出我的推导错误，或解释为何时间复杂度是O(n²·n!)，感谢帮助！

解答 #

你的推导核心错误在于忽略了字符串拼接操作的累计时间开销，以下是具体解释：

• 递归调用次数的误区
  你认为总共有n!次递归调用是不准确的——实际递归调用总次数是sum_{k=1 to n} P(n,k)（P(n,k)为n选k的排列数），这个和趋近于e·n!，但这不是关键。真正影响复杂度的是，不同层级的递归调用中，字符串操作的开销不能用“单次O(n)”简单概括。

• 字符串操作的实际成本
  代码中的str.substring和字符串拼接（+）都是线性时间操作：

  • 生成rem时，str.substring(0,i)和str.substring(i+1)的总长度等于原str长度减1，拼接它们需要O(m)时间（m为当前str的长度）；
  • 生成新的prefix时，prefix + str.charAt(i)需要O(k)时间（k为当前prefix的长度）。
    对于每个排列来说，生成它需要经历n次递归拼接，每次拼接的长度从1到n，累计开销为1+2+...+n = O(n²)。而总共有n!个排列，因此总时间复杂度为O(n²·n!)。

• 用具体数值验证
  以n=3为例：

  • 总递归调用次数为1+3+6+6=16次；
  • 各层级调用的字符串操作开销：
    • str长度3的调用：3次循环，每次操作O(3)，总开销3*3=9；
    • str长度2的调用：6次循环，每次操作O(3)，总开销6*3=18；
    • str长度1的调用：6次循环，每次操作O(3)，总开销6*3=18；
  • 总开销为9+18+18=45，而n²·n! = 9*6=54，大O表示法忽略常数项，两者属于同一复杂度级别。
    而按你的推导（n!次调用O(n)）得到63=18，远小于实际开销，足以说明推导漏洞。

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