为什么这个例子的时间复杂度从"Cracking the Coding Interview"O(k c^k)？
Why is the time complexity of this example from "Cracking the Coding Interview" O(k c^k)?
本题出自Cracking the Coding Interview第6版，题目V1.11。
The following code prints all strings of length k where the characters
are in sorted order. It does this by generating all strings of length
k and then checking if each is sorted. What is the runtime?
package QVI_11_Print_Sorted_Strings;
public class Question {
public static int numChars = 26;
public static void printSortedStrings(int remaining) {
printSortedStrings(remaining, "");
}
public static void printSortedStrings(int remaining, String prefix) {
if (remaining == 0) {
if (isInOrder(prefix)) {
System.out.println(prefix);
}
} else {
for (int i = 0; i < numChars; i++) {
char c = ithLetter(i);
printSortedStrings(remaining - 1, prefix + c);
}
}
}
public static boolean isInOrder(String s) {
for (int i = 1; i < s.length(); i++) {
int prev = ithLetter(s.charAt(i - 1));
int curr = ithLetter(s.charAt(i));
if (prev > curr) {
return false;
}
}
return true;
}
public static char ithLetter(int i) {
return (char) (((int) 'a') + i);
}
public static void main(String[] args) {
printSortedStrings(5);
}
}
The answer is O(k c^k) where k is the length of the string and c is
the number of characters in the alphabet. It takes O(c^k) time to
generate each string. Then, we need to check that each of these is
sorted, which takes O(k) time.
现在，我明白 O(k) 是从哪里来的，但我不明白 O(c^k) 是怎么来的。
上述算法的工作原理是使用一组 c 个字符选择递归地生成所有可能的长度为 k 的字符串。你可以从 c 个字母中选择长度为 k 的可能字符串的数量等于 ck。例如，如果我有两个字母可供选择（a 和 b）并且我有长度为 3 的字符串，那么我可以制作 23 = 8 个可能的字符串：
- aaa
- aab
- 阿巴
- abb
- 咩
- 巴布
- bba
- bbb
为了更好地了解这是从哪里来的，请注意每次在字符串末尾添加一个新字母时，您都有 c 个选项可以选择该字母，因此可能的字符串数为
c · c · ... · c (k times) =
ck
这意味着上面的代码通过生成这些字符串中的每一个来工作，必须至少Ω(ck)有效，因为这是要检查的最少字符串数。
那么它为每个字符串做了多少工作？这就是事情变得棘手的地方。这些字符串是通过不断地从可能字符列表中附加一个新字符而一次构建一个字符的。在 Java 中，附加到字符串会生成字符串的完整副本，因此附加第一个字符的成本（大约）为 1，第二个字符（大约）为 2，然后是 3，然后是 4，依此类推。意味着构建一个长度为 k 的完整字符串的成本将是
1 + 2 + 3 + ... + k
= Θ(k2)
所以这里的运行时间实际上看起来是 O(ck k2) 而不是 O(k ck), 因为构建所有这些字符串的成本加起来相当快。
然而，这并不是一个严格的界限。例如，形成字符串 aaa 所做的一些工作也用于形成字符串 aab，因为这两个字符串都是通过以 aa 开头并连接另一个字符形成的。
为了获得更好的分析，我们可以总结在树中的每个级别执行串联所完成的总工作量。树的第 0 层有一个大小为 0 的字符串，因此没有进行任何连接。树的第一层有 c 个大小为 1 的字符串，需要进行 c 次连接操作。树的第二层有 c2 个大小为 2 的字符串，需要 2c2 才能形成。三层中的第三层有 c3 个大小为 3 的字符串，需要 3c3 才能形成。更一般地说，级别 i 需要 ici 工作才能形成。这意味着我们要确定
0c0 + 1c1 + 2c2 + ... + kck.
此求和结果为 Θ(kck)，其中 k 项的指数较低。
总结一下：
- ck项来自需要检查的字符串数。
- 第 k 项来自每个字符串完成的工作。
- 仔细分析一下，生成所有这些字符串的时间并不影响O(k ck)的整体运行时间。
我认为他们没有考虑书中的 k^2，因为实际书中的代码没有写在 Java 中。因此可以安全地假设字符串连接是 O(1)。另外，书上的答案解释也不是最好的。生成每个字符串只需要 O(k) 时间，但有 O(c^k) 个可能的字符串。并且需要 O(k) 来验证结果，因此它应该是 O(k^2 c^k) 而不是 O(kc^k) （具有 O(1) 字符串连接时间）。但是，您应该与面试官讨论，只需询问打印、串联等是否需要 O(1) 时间或更长时间。
对printSortedStrings的递归调用形成了递归树。因为节点总数大约是最低层节点数的一个常数因子，而上层并没有比最低层做更多的工作，所以只有最低层的成本是显着的。
举个例子，c是2，k是3：
查看生成的树的第一层：
2（或2^1）个字符串，"a"，"b".
二级产出：
4（或2^2）字符串，"aa"，"ab"，"ba"，"bb".
第三关产出：
8（或2^3）字符串，"aaa"，"aab"，"aba"，"abb"，"baa"， "bab", "bba", "bbb".
按顺序生成下一个字符串的成本是线性的。旧字符串中的字符加上新字符被复制到新字符串中。
这取决于字符串的长度，所以第一层的成本是1，第二层的成本是2，第三层的成本是3。乘以每一层的项目数：
(2^1)*1 + (2^2)*2 + (2^3)*3 = 34
如果 k 为 4，则此模式将继续：
(2^1)*1 + (2^2)*2 + (2^3)*3 + (2^4)*4 = 98
关于这样的求和，就是最后一项大于所有前面各项的总和。所以只有最后一项是重要的：
(2^1)*1 + (2^2)*2 + (2^3)*3 < (2^4)*4
因为：
(2^1)*1 + (2^2)*2 + (2^3)*3
< (2^1)*3 + (2^2)*3 + (2^3)*3
= (2^1 + 2^2 + 2^3) * 3
= (2^4 - 2) * 3
< (2^4 - 2) * 4
< (2^4) * 4
所以总和小于2*(2^4)*4，或2*(c^k)*k，或O(k c^k)。
在递归结束时，有更多的线性时间工作。有 c^k 个节点的 k 工作给出了另一个 O(k c^k) 成本。所以总成本还是O(k c^k).
另一件事是 for 循环对每个字符串也需要线性时间，但出于与上述类似的原因，这总共需要 O(k c^k)。
本题出自Cracking the Coding Interview第6版，题目V1.11。
The following code prints all strings of length k where the characters are in sorted order. It does this by generating all strings of length k and then checking if each is sorted. What is the runtime?
package QVI_11_Print_Sorted_Strings;
public class Question {
public static int numChars = 26;
public static void printSortedStrings(int remaining) {
printSortedStrings(remaining, "");
}
public static void printSortedStrings(int remaining, String prefix) {
if (remaining == 0) {
if (isInOrder(prefix)) {
System.out.println(prefix);
}
} else {
for (int i = 0; i < numChars; i++) {
char c = ithLetter(i);
printSortedStrings(remaining - 1, prefix + c);
}
}
}
public static boolean isInOrder(String s) {
for (int i = 1; i < s.length(); i++) {
int prev = ithLetter(s.charAt(i - 1));
int curr = ithLetter(s.charAt(i));
if (prev > curr) {
return false;
}
}
return true;
}
public static char ithLetter(int i) {
return (char) (((int) 'a') + i);
}
public static void main(String[] args) {
printSortedStrings(5);
}
}
The answer is O(k c^k) where k is the length of the string and c is the number of characters in the alphabet. It takes O(c^k) time to generate each string. Then, we need to check that each of these is sorted, which takes O(k) time.
现在，我明白 O(k) 是从哪里来的，但我不明白 O(c^k) 是怎么来的。
上述算法的工作原理是使用一组 c 个字符选择递归地生成所有可能的长度为 k 的字符串。你可以从 c 个字母中选择长度为 k 的可能字符串的数量等于 ck。例如，如果我有两个字母可供选择（a 和 b）并且我有长度为 3 的字符串，那么我可以制作 23 = 8 个可能的字符串：
- aaa
- aab
- 阿巴
- abb
- 咩
- 巴布
- bba
- bbb
为了更好地了解这是从哪里来的，请注意每次在字符串末尾添加一个新字母时，您都有 c 个选项可以选择该字母，因此可能的字符串数为
c · c · ... · c (k times) =
ck
这意味着上面的代码通过生成这些字符串中的每一个来工作，必须至少Ω(ck)有效，因为这是要检查的最少字符串数。
那么它为每个字符串做了多少工作？这就是事情变得棘手的地方。这些字符串是通过不断地从可能字符列表中附加一个新字符而一次构建一个字符的。在 Java 中，附加到字符串会生成字符串的完整副本，因此附加第一个字符的成本（大约）为 1，第二个字符（大约）为 2，然后是 3，然后是 4，依此类推。意味着构建一个长度为 k 的完整字符串的成本将是
1 + 2 + 3 + ... + k
= Θ(k2)
所以这里的运行时间实际上看起来是 O(ck k2) 而不是 O(k ck), 因为构建所有这些字符串的成本加起来相当快。
然而，这并不是一个严格的界限。例如，形成字符串 aaa 所做的一些工作也用于形成字符串 aab，因为这两个字符串都是通过以 aa 开头并连接另一个字符形成的。
为了获得更好的分析，我们可以总结在树中的每个级别执行串联所完成的总工作量。树的第 0 层有一个大小为 0 的字符串，因此没有进行任何连接。树的第一层有 c 个大小为 1 的字符串，需要进行 c 次连接操作。树的第二层有 c2 个大小为 2 的字符串，需要 2c2 才能形成。三层中的第三层有 c3 个大小为 3 的字符串，需要 3c3 才能形成。更一般地说，级别 i 需要 ici 工作才能形成。这意味着我们要确定
0c0 + 1c1 + 2c2 + ... + kck.
此求和结果为 Θ(kck)，其中 k 项的指数较低。
总结一下：
- ck项来自需要检查的字符串数。
- 第 k 项来自每个字符串完成的工作。
- 仔细分析一下，生成所有这些字符串的时间并不影响O(k ck)的整体运行时间。
我认为他们没有考虑书中的 k^2，因为实际书中的代码没有写在 Java 中。因此可以安全地假设字符串连接是 O(1)。另外，书上的答案解释也不是最好的。生成每个字符串只需要 O(k) 时间，但有 O(c^k) 个可能的字符串。并且需要 O(k) 来验证结果，因此它应该是 O(k^2 c^k) 而不是 O(kc^k) （具有 O(1) 字符串连接时间）。但是，您应该与面试官讨论，只需询问打印、串联等是否需要 O(1) 时间或更长时间。
对printSortedStrings的递归调用形成了递归树。因为节点总数大约是最低层节点数的一个常数因子，而上层并没有比最低层做更多的工作，所以只有最低层的成本是显着的。
举个例子，c是2，k是3：
查看生成的树的第一层：
2（或2^1）个字符串，"a"，"b".
二级产出：
4（或2^2）字符串，"aa"，"ab"，"ba"，"bb".
第三关产出：
8（或2^3）字符串，"aaa"，"aab"，"aba"，"abb"，"baa"， "bab", "bba", "bbb".
按顺序生成下一个字符串的成本是线性的。旧字符串中的字符加上新字符被复制到新字符串中。
这取决于字符串的长度，所以第一层的成本是1，第二层的成本是2，第三层的成本是3。乘以每一层的项目数：
(2^1)*1 + (2^2)*2 + (2^3)*3 = 34
如果 k 为 4，则此模式将继续：
(2^1)*1 + (2^2)*2 + (2^3)*3 + (2^4)*4 = 98
关于这样的求和，就是最后一项大于所有前面各项的总和。所以只有最后一项是重要的：
(2^1)*1 + (2^2)*2 + (2^3)*3 < (2^4)*4
因为：
(2^1)*1 + (2^2)*2 + (2^3)*3
< (2^1)*3 + (2^2)*3 + (2^3)*3
= (2^1 + 2^2 + 2^3) * 3
= (2^4 - 2) * 3
< (2^4 - 2) * 4
< (2^4) * 4
所以总和小于2*(2^4)*4，或2*(c^k)*k，或O(k c^k)。
在递归结束时，有更多的线性时间工作。有 c^k 个节点的 k 工作给出了另一个 O(k c^k) 成本。所以总成本还是O(k c^k).
另一件事是 for 循环对每个字符串也需要线性时间，但出于与上述类似的原因，这总共需要 O(k c^k)。