以下代码打印字符串的所有排列:
void permutation(String str) {
permutation(str, "");
}
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));
}
}
}
GeeksForGeeks通过确定以下各项来分析代码的时间复杂度:
- 该函数在其基本情况下被调用
n!次 - for循环运行
n次 - 因此，递归树中的阶乘 node 不会超过
n * n!个. - 每个函数调用对应
O(n)个工作，因此总时间复杂度为O(n2*n！).
我知道时间复杂度可以通过将递归树中的 node 数乘以每个函数调用所做的工作量来估计.如果我使用Branchsdepth公式来估计递归树中的 node 数，我会在递归树中得到n个n个 node ，这与n * n!个非常不同.
我想知道为什么Branchsdepth对于这个问题不是一个严格的界限，在这种情况下，我不应该使用O(Branchsdepth)来估计一个函数进行多个调用的时间复杂度.
