字符串子序列递归的时间复杂度
Time Complexity of String Subsequence Recursion
如何计算下面算法的时间复杂度？有人可以简单地给我解释一下吗：
public static void print(String prefix, String remaining, int k) {
if (k == 0) {
StdOut.println(prefix);
return;
}
if (remaining.length() == 0) return;
print(prefix + remaining.charAt(0), remaining.substring(1), k-1);
print(prefix, remaining.substring(1), k);
}
public static void main(String[] args) {
String s = "abcdef";
int k = 3;
print("", s, k);
}
假设m是prefix的长度，n是remaining的长度。那么复杂度由
给出
T(m, n, k) = Θ(m + n) + T(m + 1, n - 1, k - 1) + T(m, n - 1, k ).
Θ(m + n) 项源于
prefix + remaining.charAt(0), remaining.substring(1)
这通常需要创建两个长度分别约为 m 和 n 的新字符串（这可能因不同的实现而不同).
除此之外，它很难解决（至少对我而言），除了一些非常简单的界限。例如，很明显，复杂度至少是前缀长度和 k 中最小值的指数，因为
T(m, n, k) ≥ 2 T(m, n - 1, k - 1) ↠ T(m, n, k) = Ω(2min(n, k)).
假设m是prefix的长度，n是remaining的长度。那么复杂度由
给出
T(m, n, k) = 1 + n + 1 + T(m + 1, n - 1, k - 1) + T(m, n - 1, k)
显然，当n=0 或k=0 时函数停止。所以，
T(r, n, 0) = 1 + r
T(m, 0, k) = 1 + 1 + 1 = 3
改造方程式1，得到
T(m, n, k) - T(m, n - 1, k) = 2 + n + T(m + 1, n - 1, k - 1)
将等式1中的n替换为n-1
T(m, n - 1, k) - T(m, n - 2, k) = 2 + (n - 1) + T(m + 1, n - 2, k - 1)
... continue ...
T(m, 1, k) - T(m, 0, k) = 2 + (1) + T(m + 1, 0, k - 1)
总结一下
T(m, n, k) - T(m, 0, k) = 2(n) + (n-1)(n)/2 + {Summation of a from 0 to n - 1 on T(m + 1, a, k - 1)}
改革
T(m, n, k) = n2/2 + 3n/2 +3 + {Summation of a from 0 to n - 1 on T(m + 1, a, k - 1)}
我想我们可以通过使用最后一个方程求解求和来得到答案，方程的主导因子类似于 nk+1
简介
因为body是O(1)，或者至少可以改写成O(1)，我们只需要看函数被调用了多少次。因此，该算法的时间复杂度将是调用函数的次数与输入字的长度和输出前缀的长度有关。
n - 输入字的长度
k - 搜索的前缀长度
我以前从未做过这样的事情，我知道的用于查找递归方法时间复杂度的常用方法在这种情况下不起作用。我首先查看根据 n 和 k 对函数进行了多少次调用，看看我是否能发现任何可能对我有帮助的模式。
收集数据
使用此代码片段（抱歉代码太丑）：
public static String word = "abcdefghij";
public static int wordLength = word.length();
public static int limit = 10;
public static int access = 0;
System.out.printf("Word length : %6d %6d %6d %6d %6d %6d %6d %6d %6d %6d %6d\n",0,1,2,3,4,5,6,7,8,9,10);
System.out.printf("-----------------------------------------------------------------------------------------------\n");
for(int k = 0; k <= limit; k++) {
System.out.printf("k : %2d - results :", k);
for(int i = 0; i <= limit; i++) {
print("", word.substring(0,i), k);
System.out.printf(", %5d", access);
access=0;
}
System.out.print("\n");
}
print(prefix, remaining, k) {
access++;
... rest of code...
}
由此我得到：
Word length : 0 1 2 3 4 5 6 7 8 9 10
-----------------------------------------------------------------------------------------------
k : 0 - results :, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
k : 1 - results :, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21
k : 2 - results :, 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111
k : 3 - results :, 1, 3, 7, 15, 29, 51, 83, 127, 185, 259, 351
k : 4 - results :, 1, 3, 7, 15, 31, 61, 113, 197, 325, 511, 771
k : 5 - results :, 1, 3, 7, 15, 31, 63, 125, 239, 437, 763, 1275
k : 6 - results :, 1, 3, 7, 15, 31, 63, 127, 253, 493, 931, 1695
k : 7 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 509, 1003, 1935
k : 8 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1021, 2025
k : 9 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2045
k : 10 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047
在每种情况下至少进行一次调用，因为它是初始调用。从这里我们看到主对角线上和下方的所有内容都被称为 2min(n, k) + 1 - 1 次，就像其他人提到的那样。那是二叉树中的节点数。
每次调用 print 方法时，都会调用两个新方法 - 生成二叉树。
虽然主对角线上方的情况变得更加混乱，但我没有看到任何共同的模式。
算法的图形表示
为了让它更直观，我使用了 graphviz (online version)。
这是为 graphviz 的给定 n 和 k 生成代码的代码片段（绿色节点是找到解决方案的节点）：
public static String word = "abcde";
public static int wordLength = word.length();
public static int limit = 3;
public static void main(String[] args) {
String rootNode = "\"prefix|remaining|k\"";
StringBuilder graph = new StringBuilder("digraph G { \n node [style=filled];");
print("", word, limit, graph, rootNode);
graph.append("\n\"prefix|remaining|k\" [shape=Mdiamond];\n}");
System.out.println(graph);
}
public static void print(String prefix, String remaining, int k, StringBuilder sb, String parent) {
String currentNode = "\"" + prefix + "|" + (remaining.isEmpty() ? 0 : remaining) + "|" + k + "\"";
sb.append("\n " + parent + "->" + currentNode + ";");
if(k == 0) {
sb.append("\n " + currentNode + "[color=darkolivegreen3];");
return;
}
if (remaining.length() == 0)return;
print(prefix + remaining.charAt(0), remaining.substring(1), k - 1, sb,currentNode);
print(prefix, remaining.substring(1), k, sb, currentNode);
}
图表示例（n=5，k=3）：
digraph G {
node [style=filled];
"prefix|remaining|k"->"|abcde|3";
"|abcde|3"->"a|bcde|2";
"a|bcde|2"->"ab|cde|1";
"ab|cde|1"->"abc|de|0";
"abc|de|0"[color=darkolivegreen3];
"ab|cde|1"->"ab|de|1";
"ab|de|1"->"abd|e|0";
"abd|e|0"[color=darkolivegreen3];
"ab|de|1"->"ab|e|1";
"ab|e|1"->"abe|0|0";
"abe|0|0"[color=darkolivegreen3];
"ab|e|1"->"ab|0|1";
"a|bcde|2"->"a|cde|2";
"a|cde|2"->"ac|de|1";
"ac|de|1"->"acd|e|0";
"acd|e|0"[color=darkolivegreen3];
"ac|de|1"->"ac|e|1";
"ac|e|1"->"ace|0|0";
"ace|0|0"[color=darkolivegreen3];
"ac|e|1"->"ac|0|1";
"a|cde|2"->"a|de|2";
"a|de|2"->"ad|e|1";
"ad|e|1"->"ade|0|0";
"ade|0|0"[color=darkolivegreen3];
"ad|e|1"->"ad|0|1";
"a|de|2"->"a|e|2";
"a|e|2"->"ae|0|1";
"a|e|2"->"a|0|2";
"|abcde|3"->"|bcde|3";
"|bcde|3"->"b|cde|2";
"b|cde|2"->"bc|de|1";
"bc|de|1"->"bcd|e|0";
"bcd|e|0"[color=darkolivegreen3];
"bc|de|1"->"bc|e|1";
"bc|e|1"->"bce|0|0";
"bce|0|0"[color=darkolivegreen3];
"bc|e|1"->"bc|0|1";
"b|cde|2"->"b|de|2";
"b|de|2"->"bd|e|1";
"bd|e|1"->"bde|0|0";
"bde|0|0"[color=darkolivegreen3];
"bd|e|1"->"bd|0|1";
"b|de|2"->"b|e|2";
"b|e|2"->"be|0|1";
"b|e|2"->"b|0|2";
"|bcde|3"->"|cde|3";
"|cde|3"->"c|de|2";
"c|de|2"->"cd|e|1";
"cd|e|1"->"cde|0|0";
"cde|0|0"[color=darkolivegreen3];
"cd|e|1"->"cd|0|1";
"c|de|2"->"c|e|2";
"c|e|2"->"ce|0|1";
"c|e|2"->"c|0|2";
"|cde|3"->"|de|3";
"|de|3"->"d|e|2";
"d|e|2"->"de|0|1";
"d|e|2"->"d|0|2";
"|de|3"->"|e|3";
"|e|3"->"e|0|2";
"|e|3"->"|0|3";
"prefix|remaining|k" [shape=Mdiamond];
}
从二叉树中切出的节点数
从n = 5和k = 3的例子中我们可以看到高度为3的树和三棵高度为2的树被砍掉了。当我们访问这些树的每一个根节点时，我们得到从完整二叉树中切出的节点数为 1*(23 - 2) + 3*(22 - 2) = 12
如果它是一棵完整的二叉树：25 + 1 - 1 = 63
节点数（调用函数 "print"）然后达到 63 - 12 = 51
结果与我们通过计算当 n = 5 和 k = 3 时调用函数的次数得到的结果相匹配。
现在我们必须找出对于每个 n 和 k，树被砍掉了多少和多大的部分。
从这里开始，我将把方法调用 print(prefix + remaining.charAt(0), remaining.substring(1), k-1); 称为左路径或左节点（就像在 graphviz 图中一样），将 print(prefix, remaining.substring(1), k); 称为右路径或右节点。
我们可以看到第一棵，当我们向左走 k 次时，最大的树被砍掉了，树的高度将为 n - k + 1。（+1 因为我们访问了我们砍掉的树的根） .
我们可以看到，无论我们之前走了多少条正确的路径（或以什么顺序），每次我们走左路 k 次我们都会得到结果。除非在我们得到 k 条左路径之前单词用完了字母。所以我们最多可以右转n-k次。
让我们仔细看看 n = 5 和 k = 3 的示例：
L - 左侧路径
R - 右路
我们砍的第一棵树走的路：
LLL
将被砍伐的下一个最高的树将是我们只取一个右节点的树，可能的组合是：
RLLL, LRLL, LLRL, LLLR -> 三棵高度为 2 的树 cut
这里我们必须注意 LLLR 已经被切割，因为 LLL 在上一步给出了解决方案。
为了获得下一棵树的数量（高度 1 -> 0 节点切割），我们将计算两个右和三个左减去已访问路径的可能组合。
组合(5,3) - 组合(4,3) = 10 - 4 = 6 个高度为 1
的节点
我们可以看到数字与示例图中的绿色节点匹配。
C(n,k) - 来自 n
的 k 的组合
f(n,k) - 算法未访问的二叉树节点数
f(n,k) = (2n-k+1-2) + Σn-ki=1(2n-k-i+1-2)(C(k+i,k) - C( k+i-1,k))
解释：
- (2n-k+1-2) - 最高的树切割，必须将其从求和中取出，否则我们将不得不取负阶乘
- Σn-ki=1 - 所有节点切割的总和，不包括已经添加的最高树。 （我们先开始添加更大的树）
- (2n-k-i+1-2) - 每棵树切割的节点数。 n-k+1 是最大的树，然后从那里向下直到高度为 "n-k-(n-k)+1 = 1"
的树
- (C(k+i,k) - C(k+i-1,k)) - 找出有多少棵给定高度的树。首先找到所有可能的路径（左边和右边），然后减去已经访问过的路径（在前面的步骤中）。
看起来很糟糕，但如果我们假设 k != 0 （如果我们不假设会有负数的阶乘 - 这是未定义的）
简化函数：
f(n,k) = Σn-ki=0(2n-k-i +1-2)*C(k+i-1,k-1)
交流评价尿酸盐时间复杂度
函数的时间复杂度：
O(2n- Σn-ki=0(2n-k-i+1-2)*C(k+i-1,k-1))
现在这看起来很糟糕并且没有提供太多信息。我不知道如何进一步简化它。我问过 here。不过到目前为止还没有答案。
但是是否值得考虑 f(n,k) 部分？可能取决于应用它的特定应用程序。我们可以从数据中看出 table 根据 n 和 k 的选择，它可以显着影响算法调用。
为了更直观地了解额外部分对复杂度的影响程度，我在图表上绘制了最佳时间复杂度和实际复杂度。
O(2n- Σn-ki=0(2n-k-i+1-2)*C(k+i-1,k-1))为彩色面
B(2min(n,k))为绿色面
我们可以看到 B(2min(n,k)) 高估了（告诉它比实际效果好得多）函数复杂度。查看算法的最坏情况复杂度通常很有用，即 W(2max(n,k))
O(2n- Σn-ki=0(2n-k-i+1-2)*C(k+i-1,k-1))为彩色面
B(2min(n,k))为绿色面
W(2max(n,k))为黄色面
结论
- 最佳情况复杂度：B(2min(n,k))
- 精确复杂度：O(2n- Σn-ki=0(2n-k-i+1-2)*C(k+i-1,k-1))
- 最坏情况复杂度：W(2max(n,k)) -> 通常记为 O(2max(n,k))
在我看来，最坏情况下的复杂度应该用来评估函数，因为准确度太复杂，如果不进一步分析就无法理解它的含义。我不会使用最好的情况复杂性，因为它留下了太多机会。不幸的是，我无法为此计算平均复杂度。根据算法的应用，使用平均值可能更适合算法评估。
如何计算下面算法的时间复杂度？有人可以简单地给我解释一下吗：
public static void print(String prefix, String remaining, int k) {
if (k == 0) {
StdOut.println(prefix);
return;
}
if (remaining.length() == 0) return;
print(prefix + remaining.charAt(0), remaining.substring(1), k-1);
print(prefix, remaining.substring(1), k);
}
public static void main(String[] args) {
String s = "abcdef";
int k = 3;
print("", s, k);
}
假设m是prefix的长度，n是remaining的长度。那么复杂度由
T(m, n, k) = Θ(m + n) + T(m + 1, n - 1, k - 1) + T(m, n - 1, k ).
Θ(m + n) 项源于
prefix + remaining.charAt(0), remaining.substring(1)
这通常需要创建两个长度分别约为 m 和 n 的新字符串（这可能因不同的实现而不同).
除此之外，它很难解决（至少对我而言），除了一些非常简单的界限。例如，很明显，复杂度至少是前缀长度和 k 中最小值的指数，因为
T(m, n, k) ≥ 2 T(m, n - 1, k - 1) ↠ T(m, n, k) = Ω(2min(n, k)).
假设m是prefix的长度，n是remaining的长度。那么复杂度由
T(m, n, k) = 1 + n + 1 + T(m + 1, n - 1, k - 1) + T(m, n - 1, k)
显然，当n=0 或k=0 时函数停止。所以，
T(r, n, 0) = 1 + r
T(m, 0, k) = 1 + 1 + 1 = 3
改造方程式1，得到
T(m, n, k) - T(m, n - 1, k) = 2 + n + T(m + 1, n - 1, k - 1)
将等式1中的n替换为n-1
T(m, n - 1, k) - T(m, n - 2, k) = 2 + (n - 1) + T(m + 1, n - 2, k - 1)
... continue ...
T(m, 1, k) - T(m, 0, k) = 2 + (1) + T(m + 1, 0, k - 1)
总结一下
T(m, n, k) - T(m, 0, k) = 2(n) + (n-1)(n)/2 + {Summation of a from 0 to n - 1 on T(m + 1, a, k - 1)}
改革
T(m, n, k) = n2/2 + 3n/2 +3 + {Summation of a from 0 to n - 1 on T(m + 1, a, k - 1)}
我想我们可以通过使用最后一个方程求解求和来得到答案，方程的主导因子类似于 nk+1
简介
因为body是O(1)，或者至少可以改写成O(1)，我们只需要看函数被调用了多少次。因此，该算法的时间复杂度将是调用函数的次数与输入字的长度和输出前缀的长度有关。
n - 输入字的长度
k - 搜索的前缀长度
我以前从未做过这样的事情，我知道的用于查找递归方法时间复杂度的常用方法在这种情况下不起作用。我首先查看根据 n 和 k 对函数进行了多少次调用，看看我是否能发现任何可能对我有帮助的模式。
收集数据
使用此代码片段（抱歉代码太丑）：
public static String word = "abcdefghij";
public static int wordLength = word.length();
public static int limit = 10;
public static int access = 0;
System.out.printf("Word length : %6d %6d %6d %6d %6d %6d %6d %6d %6d %6d %6d\n",0,1,2,3,4,5,6,7,8,9,10);
System.out.printf("-----------------------------------------------------------------------------------------------\n");
for(int k = 0; k <= limit; k++) {
System.out.printf("k : %2d - results :", k);
for(int i = 0; i <= limit; i++) {
print("", word.substring(0,i), k);
System.out.printf(", %5d", access);
access=0;
}
System.out.print("\n");
}
print(prefix, remaining, k) {
access++;
... rest of code...
}
由此我得到：
Word length : 0 1 2 3 4 5 6 7 8 9 10
-----------------------------------------------------------------------------------------------
k : 0 - results :, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
k : 1 - results :, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21
k : 2 - results :, 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111
k : 3 - results :, 1, 3, 7, 15, 29, 51, 83, 127, 185, 259, 351
k : 4 - results :, 1, 3, 7, 15, 31, 61, 113, 197, 325, 511, 771
k : 5 - results :, 1, 3, 7, 15, 31, 63, 125, 239, 437, 763, 1275
k : 6 - results :, 1, 3, 7, 15, 31, 63, 127, 253, 493, 931, 1695
k : 7 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 509, 1003, 1935
k : 8 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1021, 2025
k : 9 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2045
k : 10 - results :, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047
在每种情况下至少进行一次调用，因为它是初始调用。从这里我们看到主对角线上和下方的所有内容都被称为 2min(n, k) + 1 - 1 次，就像其他人提到的那样。那是二叉树中的节点数。 每次调用 print 方法时，都会调用两个新方法 - 生成二叉树。
虽然主对角线上方的情况变得更加混乱，但我没有看到任何共同的模式。
算法的图形表示
为了让它更直观，我使用了 graphviz (online version)。
这是为 graphviz 的给定 n 和 k 生成代码的代码片段（绿色节点是找到解决方案的节点）：
public static String word = "abcde";
public static int wordLength = word.length();
public static int limit = 3;
public static void main(String[] args) {
String rootNode = "\"prefix|remaining|k\"";
StringBuilder graph = new StringBuilder("digraph G { \n node [style=filled];");
print("", word, limit, graph, rootNode);
graph.append("\n\"prefix|remaining|k\" [shape=Mdiamond];\n}");
System.out.println(graph);
}
public static void print(String prefix, String remaining, int k, StringBuilder sb, String parent) {
String currentNode = "\"" + prefix + "|" + (remaining.isEmpty() ? 0 : remaining) + "|" + k + "\"";
sb.append("\n " + parent + "->" + currentNode + ";");
if(k == 0) {
sb.append("\n " + currentNode + "[color=darkolivegreen3];");
return;
}
if (remaining.length() == 0)return;
print(prefix + remaining.charAt(0), remaining.substring(1), k - 1, sb,currentNode);
print(prefix, remaining.substring(1), k, sb, currentNode);
}
图表示例（n=5，k=3）：
digraph G {
node [style=filled];
"prefix|remaining|k"->"|abcde|3";
"|abcde|3"->"a|bcde|2";
"a|bcde|2"->"ab|cde|1";
"ab|cde|1"->"abc|de|0";
"abc|de|0"[color=darkolivegreen3];
"ab|cde|1"->"ab|de|1";
"ab|de|1"->"abd|e|0";
"abd|e|0"[color=darkolivegreen3];
"ab|de|1"->"ab|e|1";
"ab|e|1"->"abe|0|0";
"abe|0|0"[color=darkolivegreen3];
"ab|e|1"->"ab|0|1";
"a|bcde|2"->"a|cde|2";
"a|cde|2"->"ac|de|1";
"ac|de|1"->"acd|e|0";
"acd|e|0"[color=darkolivegreen3];
"ac|de|1"->"ac|e|1";
"ac|e|1"->"ace|0|0";
"ace|0|0"[color=darkolivegreen3];
"ac|e|1"->"ac|0|1";
"a|cde|2"->"a|de|2";
"a|de|2"->"ad|e|1";
"ad|e|1"->"ade|0|0";
"ade|0|0"[color=darkolivegreen3];
"ad|e|1"->"ad|0|1";
"a|de|2"->"a|e|2";
"a|e|2"->"ae|0|1";
"a|e|2"->"a|0|2";
"|abcde|3"->"|bcde|3";
"|bcde|3"->"b|cde|2";
"b|cde|2"->"bc|de|1";
"bc|de|1"->"bcd|e|0";
"bcd|e|0"[color=darkolivegreen3];
"bc|de|1"->"bc|e|1";
"bc|e|1"->"bce|0|0";
"bce|0|0"[color=darkolivegreen3];
"bc|e|1"->"bc|0|1";
"b|cde|2"->"b|de|2";
"b|de|2"->"bd|e|1";
"bd|e|1"->"bde|0|0";
"bde|0|0"[color=darkolivegreen3];
"bd|e|1"->"bd|0|1";
"b|de|2"->"b|e|2";
"b|e|2"->"be|0|1";
"b|e|2"->"b|0|2";
"|bcde|3"->"|cde|3";
"|cde|3"->"c|de|2";
"c|de|2"->"cd|e|1";
"cd|e|1"->"cde|0|0";
"cde|0|0"[color=darkolivegreen3];
"cd|e|1"->"cd|0|1";
"c|de|2"->"c|e|2";
"c|e|2"->"ce|0|1";
"c|e|2"->"c|0|2";
"|cde|3"->"|de|3";
"|de|3"->"d|e|2";
"d|e|2"->"de|0|1";
"d|e|2"->"d|0|2";
"|de|3"->"|e|3";
"|e|3"->"e|0|2";
"|e|3"->"|0|3";
"prefix|remaining|k" [shape=Mdiamond];
}
从二叉树中切出的节点数
从n = 5和k = 3的例子中我们可以看到高度为3的树和三棵高度为2的树被砍掉了。当我们访问这些树的每一个根节点时，我们得到从完整二叉树中切出的节点数为 1*(23 - 2) + 3*(22 - 2) = 12
如果它是一棵完整的二叉树：25 + 1 - 1 = 63
节点数（调用函数 "print"）然后达到 63 - 12 = 51
结果与我们通过计算当 n = 5 和 k = 3 时调用函数的次数得到的结果相匹配。
现在我们必须找出对于每个 n 和 k，树被砍掉了多少和多大的部分。
从这里开始，我将把方法调用 print(prefix + remaining.charAt(0), remaining.substring(1), k-1); 称为左路径或左节点（就像在 graphviz 图中一样），将 print(prefix, remaining.substring(1), k); 称为右路径或右节点。
我们可以看到第一棵，当我们向左走 k 次时，最大的树被砍掉了，树的高度将为 n - k + 1。（+1 因为我们访问了我们砍掉的树的根） .
我们可以看到，无论我们之前走了多少条正确的路径（或以什么顺序），每次我们走左路 k 次我们都会得到结果。除非在我们得到 k 条左路径之前单词用完了字母。所以我们最多可以右转n-k次。
让我们仔细看看 n = 5 和 k = 3 的示例：
L - 左侧路径
R - 右路
我们砍的第一棵树走的路：
LLL
将被砍伐的下一个最高的树将是我们只取一个右节点的树，可能的组合是：
RLLL, LRLL, LLRL, LLLR -> 三棵高度为 2 的树 cut
这里我们必须注意 LLLR 已经被切割，因为 LLL 在上一步给出了解决方案。
为了获得下一棵树的数量（高度 1 -> 0 节点切割），我们将计算两个右和三个左减去已访问路径的可能组合。
组合(5,3) - 组合(4,3) = 10 - 4 = 6 个高度为 1
的节点
我们可以看到数字与示例图中的绿色节点匹配。
C(n,k) - 来自 n
的 k 的组合
f(n,k) - 算法未访问的二叉树节点数
f(n,k) = (2n-k+1-2) + Σn-ki=1(2n-k-i+1-2)(C(k+i,k) - C( k+i-1,k))
解释：
- (2n-k+1-2) - 最高的树切割，必须将其从求和中取出，否则我们将不得不取负阶乘
- Σn-ki=1 - 所有节点切割的总和，不包括已经添加的最高树。 （我们先开始添加更大的树）
- (2n-k-i+1-2) - 每棵树切割的节点数。 n-k+1 是最大的树，然后从那里向下直到高度为 "n-k-(n-k)+1 = 1" 的树
- (C(k+i,k) - C(k+i-1,k)) - 找出有多少棵给定高度的树。首先找到所有可能的路径（左边和右边），然后减去已经访问过的路径（在前面的步骤中）。
看起来很糟糕，但如果我们假设 k != 0 （如果我们不假设会有负数的阶乘 - 这是未定义的）
简化函数：
f(n,k) = Σn-ki=0(2n-k-i +1-2)*C(k+i-1,k-1)
交流评价尿酸盐时间复杂度
函数的时间复杂度：
O(2n- Σn-ki=0(2n-k-i+1-2)*C(k+i-1,k-1))
现在这看起来很糟糕并且没有提供太多信息。我不知道如何进一步简化它。我问过 here。不过到目前为止还没有答案。
但是是否值得考虑 f(n,k) 部分？可能取决于应用它的特定应用程序。我们可以从数据中看出 table 根据 n 和 k 的选择，它可以显着影响算法调用。
为了更直观地了解额外部分对复杂度的影响程度，我在图表上绘制了最佳时间复杂度和实际复杂度。
B(2min(n,k))为绿色面
我们可以看到 B(2min(n,k)) 高估了（告诉它比实际效果好得多）函数复杂度。查看算法的最坏情况复杂度通常很有用，即 W(2max(n,k))
B(2min(n,k))为绿色面
W(2max(n,k))为黄色面
结论
- 最佳情况复杂度：B(2min(n,k))
- 精确复杂度：O(2n- Σn-ki=0(2n-k-i+1-2)*C(k+i-1,k-1))
- 最坏情况复杂度：W(2max(n,k)) -> 通常记为 O(2max(n,k))
在我看来，最坏情况下的复杂度应该用来评估函数，因为准确度太复杂，如果不进一步分析就无法理解它的含义。我不会使用最好的情况复杂性，因为它留下了太多机会。不幸的是，我无法为此计算平均复杂度。根据算法的应用，使用平均值可能更适合算法评估。