计算字符串的所有排列(破解编码访谈,第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!).

但节点的数量不应该是:

因为调用的数量相当于节点的数量(请参阅Quinston Pimenta的视频Permutations Of String | Code Tutorial中的图).

如果我们遵循这个方法,节点的数量将是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!).