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

Question

在Gayle Laakman的书“Cracking the Coding Interview”，第六章（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！ = 16

但是，根据上述方法，节点数将为3 * 3！ = 18

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

Answer 1

你对节点的数量是正确的。该公式给出了确切的数字，但书中的方法计算了多次。

你的总和似乎也接近e * n!为大n，所以可以简化为O(n!)。

说调用次数不超过n * n!在技术上是正确的，因为这是一个有效的上限。根据使用方法的不同，这可能会很好，也可能更容易证明。

对于时间复杂度，我们需要乘以每个节点的平均工作量。

首先，检查字符串连接。每次迭代都会创建2新字符串以传递给下一个节点。一个String的长度增加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!)。