Cracking the Coding Interview例12：字符串全排列代码第7、10、11行O(n)复杂度疑问

上述全排列代码的总时间复杂度为O(n * n!)，这个结果由「全排列的总数量n!」乘以「单次排列生成、输出的耗时O(n)」计算得到，以下针对你的两个疑问分别解答：

1 第7行System.out.println(prefix)的O(n)复杂度说明 #

你的第一个猜测是正确的，复杂度来源和打印内容是否重复无关：

• 打印字符串的底层逻辑是逐个输出字符串包含的每一个字符，当递归到终止条件时，prefix的长度等于输入字符串的总长度n，所以单次打印操作的时间复杂度固定为O(n)。
• 不是所有打印语句的复杂度都是O(n)：如果打印的是长度固定的内容（比如单个字符、常量字符串），复杂度就是O(1)，只有当打印内容的长度和输入规模n正相关时，才会达到O(n)级别。
• 为什么该操作没有包含在n!项里：n!是全排列的总数量，对应你会执行n!次打印操作，每次打印耗时O(n)，所以所有打印操作的总耗时是n! * O(n) = O(n*n!)，两者是相乘关系，不是包含关系。

2 第10、11行字符串操作的O(n)复杂度说明 #

你的猜测完全正确，复杂度来源就是Java字符串的不可变特性：
Java中的String是不可变类，所有字符串拼接、截取子串的操作都需要重新复制字符数组生成新的String对象：

• 第10行的str.substring(0,i)+str.substring(i+1)：两个子串的总长度为n-1，拼接时需要把两个子串的所有字符复制到新的字符数组中，单次操作时间复杂度为O(n)。
• 第11行的prefix+str.charAt(i)：每递归一层，prefix的长度就增加1，最深层递归时prefix长度为n，单次拼接的时间和当前prefix长度正相关，所有递归层的拼接操作总耗时也在O(n*n!)量级。

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