在 Gayle Laakman 的书“Cracking the Coding Interview”,第 VI 章(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
难道我们不应该将树中的共享节点算作一个节点吗,因为它们表示一个函数调用?
最佳答案
关于节点的数量,你是对的。那个公式给出了准确的数字,但是书上的方法算了好几遍。
对于较大的 n
,您的总和似乎也接近 e * n!
,因此可以简化为 O(n!)
。
调用次数不超过 n * n!
在技术上仍然是正确的,因为这是一个有效的上限。根据其使用方式,这可能很好,并且可能更容易证明。
对于时间复杂度,我们需要乘以每个节点完成的平均工作。
首先,检查字符串连接。每次迭代都会创建 2
个新字符串以传递给下一个节点。一个String的长度增加1
,另一个的长度减少1
,但总长度总是n
,给出a每次迭代的时间复杂度为 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 !)
。
关于java - 计算字符串的所有排列(破解编码面试,第六章 - 示例 12),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44858886/