java计算字符串的所有排列（破解编码访谈，第六章示例12）

Question

在盖尔·拉克曼（Gayle Laakman）的书《破解编码面试》（Cracking the Codeing Session）第六章（Big O），示例12中，问题指出，给定以下用于计算字符串排列的Java代码，需要计算代码的复杂性

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

这本书假设，既然会有n！排列，如果我们认为每一个排列都是调用树中的一个叶子，其中每个叶子都被连接到一个长度为n的路径上，那么就不再有N*N了！树中的节点（即：调用次数不超过n*n！）

但节点的数量不应该是：

因为调用的数量相当于节点的数量（请看视频Permutations Of String | Code Tutorial by Quinston Pimenta中的图）

如果我们遵循这种方法，节点的数量将是1（对于第一级/树的根）+3（对于第二级）+3*2（对于第三级）+3*2*1（对于第四级/底层）

即：节点数=3/3! + 3!/2! + 3!/1! + 3!/0! = 十六

然而，根据上述方法，节点的数量将是3*3！=18

我们不应该将树中的共享节点计算为一个节点，因为它们表示一个函数调用吗

Answer 1

关于节点的数量，你是对的。这个公式给出了确切的数字，但书中的方法计算了好几次

对于大的n，您的总和似乎也接近e * n!，因此可以简化为O(n!)

从技术上讲，呼叫数不超过n * n!仍然是正确的，因为这是一个有效的上限。这取决于它的使用方式，这可能很好，也可能更容易证明

对于时间复杂度，我们需要乘以每个节点所做的平均功

首先，检查字符串连接。每次迭代都会创建2个新字符串传递给下一个节点。一个字符串的长度增加1，另一个字符串的长度减少1，但总长度始终为n，因此每次迭代的时间复杂度为O(n)

每个级别的迭代次数不同，所以我们不能只乘以n。而是查看整个树的总迭代次数，并获得每个节点的平均值。用n = 3

• 第一级中的1节点迭代3次：1 * 3 = 3
• 第二级中的3节点迭代2次：3 * 2 = 6
• 第三级中的6节点迭代1时间：6 * 1 = 6

迭代的总次数为：3 + 6 + 6 = 15。这与树中的节点数大致相同。所以每个节点的平均迭代次数是恒定的

总的来说，我们有O(n!)个迭代，每个迭代进行O(n)个工作，总时间复杂度为O(n * n!)

Answer 2

根据你的视频，我们有3个字符的字符串（ABC），排列的数量是6 = 3!，而6恰好等于1 + 2 + 3。然而，如果我们有一个包含4个字符的字符串（ABCD），那么排列的数量应该是4 * 3!，因为D可以位于1到4之间的任何位置。使用D的每个位置，可以为其余位置生成3!置换。如果你重新画一棵树，数一数排列的数量，你就会看到不同之处

根据你的代码，我们有n! = str.length()!个置换，但是在置换的每次调用中，你也会运行一个从0到n-1的循环。因此，你有O(n * n!)

---

更新对已编辑问题的回复

首先，在编程中，我们通常有0->n-1或1->n而不是0->n

其次，在这种情况下，我们不会计算节点的数量，因为如果再次查看片段中的递归树，就会看到重复的节点。在这种情况下，排列应该是彼此唯一的叶子数

例如，如果你有一个包含4个字符的字符串，那么叶子的数量应该是4 * 3! = 24，它应该是排列的数量。然而，在代码片段中，在每个排列中也有一个0->n-1 = 0->3循环，因此需要计算其中的循环。因此，本例中的代码复杂度为O(n *n!) = O(4 * 4!)