时间复杂度：得到不正确的结果
Time complexity : Getting incorrect result
以下代码来自"Cracking the coding interview"一书。该代码打印字符串的所有排列。
问题: 下面代码的时间复杂度是多少
void permutation(String str) {
permutation(str, "");
}
private 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!。
我确定我错过了蓝色、绿色和黄色节点的时间复杂度。但屡试不爽，始终未能明确出路。
有人可以分享一些意见吗，最好是举例说明？
时间复杂度为O(n!)。这是一个分析（复制自geeksforgeeks）。它也被称为堆算法。
复杂度分析：
- 该算法生成前
n-1 个元素的 (n-1)! 个排列，将最后一个元素与每个排列相邻。这将生成以最后一个元素结尾的所有排列。
- 如果
n为奇数，交换第一个和最后一个元素，如果n为偶数，则交换第i个元素（i是从0开始的计数器）和最后一个元素，重复上述算法直到 i 小于 n.
- 在每次迭代中，算法将生成以当前最后一个元素结尾的所有排列。
您在这里的方向非常正确，您的总体评估（运行时间为 Θ(n · n!)）是正确的！我们可以用来推导运行时的一种技术是总结树中每一层完成的工作。我们知道
- 在第0层（顶层），有1个节点处理长度为n的字符串，
- 第1层有n个节点，每个节点处理长度为n - 1的字符串，
- 在第2层，有n(n-1)个节点，每个节点处理长度为n - 2的字符串，
- 第3层，有n(n-1)(n-2)个节点，每个节点处理长度为n -3的字符串，
- ...
- 第n层，有n！每个节点处理长度为 0 的字符串。
为了计算此处完成的总工作量，我们假设每个递归调用在基线时的 O(1) 工作量，加上与其正在处理的字符串的长度成正比的工作量。这意味着我们需要计算出两个总和来确定完成的总工作量：
Sum 1: Number of Calls
1 + n + n(n-1) + n(n-1)(n-2) + ... + n!
和
Sum 2: Work Processing Strings
1 · n + n · (n-1) + n(n-1)·(n-2) + ... + n! · 0
但是还有一个因素需要考虑——每个命中基本情况的递归调用都会打印出以这种方式生成的字符串，这需要 O(n) 时间。所以这增加了 Θ(n · n!) 的最终因子。因此，完成的总工作将是 Θ(n · n!)，加上所有中间递归调用构建答案所做的工作。
让我们分别处理这些总和。
总和 1：调用次数
我们正在处理这个不寻常的金额：
1 + n + n(n-1) + n(n-1)(n-2) + ... + n!
我们需要的主要观察是
- 1 = n! /n!,
- n = n! / (n-1)!,
- n(n-1) = n! / (n-2)!
- ...
- n！ = n！ / (n-n)!
所以，换句话说，这个总和是
n! / n! + n! / (n-1)! + n! / (n-2)! + ... + n! / 0!
= n!(1 / n! + 1/(n-1)! + 1/(n-2)! + ... + 1/0!)
≤ en!
= Θ(n!)
在这里，最后一步是根据总和
1/0! + 1/1! + 1/2! + 1/3! + ...
无穷大是定义数字e的方法之一。这意味着这里进行的递归调用总数为 Θ(n!)。
而且，直觉上，这应该是有道理的。每个递归调用，除了对长度为 1 的字符串的递归调用之外，都会进行另外两次递归调用，因此递归树主要是分支的。关于树有一个很好的事实，即每个节点都有分支的树不会有比叶子更多的内部节点。因为有 n!离开时，剩余的节点数不渐近地大于 n! 就不足为奇了。
总和 2：工作处理字符串
这是总和
1 · n + n · (n-1) + n(n-1)·(n-2) + ... + n! · 0
我们可以将其重写为
n + n(n-1) + n(n-1)(n-2) + ...
嘿！我们知道那个总和——它几乎和我们刚才看到的一样。结果为 Θ(n!)。
综合考虑
总而言之，这个递归算法
- Θ(n!) 的工作仅仅是因为递归调用的次数，每次调用都需要一些基本时间；
- Θ(n!) 递归调用在形成和连接子字符串时完成的工作；和
- Θ(n · n!) 最终递归调用完成的工作，打印出所有排列。
总结这一切给出了您在问题中提出的 Θ(n · n!) 运行时间。
希望对您有所帮助！
以下代码来自"Cracking the coding interview"一书。该代码打印字符串的所有排列。
问题: 下面代码的时间复杂度是多少
void permutation(String str) {
permutation(str, "");
}
private 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!。
我确定我错过了蓝色、绿色和黄色节点的时间复杂度。但屡试不爽，始终未能明确出路。
有人可以分享一些意见吗，最好是举例说明？
时间复杂度为O(n!)。这是一个分析（复制自geeksforgeeks）。它也被称为堆算法。
复杂度分析：
- 该算法生成前
n-1个元素的(n-1)!个排列，将最后一个元素与每个排列相邻。这将生成以最后一个元素结尾的所有排列。 - 如果
n为奇数，交换第一个和最后一个元素，如果n为偶数，则交换第i个元素（i是从0开始的计数器）和最后一个元素，重复上述算法直到 i 小于 n. - 在每次迭代中，算法将生成以当前最后一个元素结尾的所有排列。
您在这里的方向非常正确，您的总体评估（运行时间为 Θ(n · n!)）是正确的！我们可以用来推导运行时的一种技术是总结树中每一层完成的工作。我们知道
- 在第0层（顶层），有1个节点处理长度为n的字符串，
- 第1层有n个节点，每个节点处理长度为n - 1的字符串，
- 在第2层，有n(n-1)个节点，每个节点处理长度为n - 2的字符串，
- 第3层，有n(n-1)(n-2)个节点，每个节点处理长度为n -3的字符串，
- ...
- 第n层，有n！每个节点处理长度为 0 的字符串。
为了计算此处完成的总工作量，我们假设每个递归调用在基线时的 O(1) 工作量，加上与其正在处理的字符串的长度成正比的工作量。这意味着我们需要计算出两个总和来确定完成的总工作量：
Sum 1: Number of Calls
1 + n + n(n-1) + n(n-1)(n-2) + ... + n!
和
Sum 2: Work Processing Strings
1 · n + n · (n-1) + n(n-1)·(n-2) + ... + n! · 0
但是还有一个因素需要考虑——每个命中基本情况的递归调用都会打印出以这种方式生成的字符串，这需要 O(n) 时间。所以这增加了 Θ(n · n!) 的最终因子。因此，完成的总工作将是 Θ(n · n!)，加上所有中间递归调用构建答案所做的工作。
让我们分别处理这些总和。
总和 1：调用次数
我们正在处理这个不寻常的金额：
1 + n + n(n-1) + n(n-1)(n-2) + ... + n!
我们需要的主要观察是
- 1 = n! /n!,
- n = n! / (n-1)!,
- n(n-1) = n! / (n-2)!
- ...
- n！ = n！ / (n-n)!
所以，换句话说，这个总和是
n! / n! + n! / (n-1)! + n! / (n-2)! + ... + n! / 0!
= n!(1 / n! + 1/(n-1)! + 1/(n-2)! + ... + 1/0!)
≤ en!
= Θ(n!)
在这里，最后一步是根据总和
1/0! + 1/1! + 1/2! + 1/3! + ...
无穷大是定义数字e的方法之一。这意味着这里进行的递归调用总数为 Θ(n!)。
而且，直觉上，这应该是有道理的。每个递归调用，除了对长度为 1 的字符串的递归调用之外，都会进行另外两次递归调用，因此递归树主要是分支的。关于树有一个很好的事实，即每个节点都有分支的树不会有比叶子更多的内部节点。因为有 n!离开时，剩余的节点数不渐近地大于 n! 就不足为奇了。
总和 2：工作处理字符串
这是总和
1 · n + n · (n-1) + n(n-1)·(n-2) + ... + n! · 0
我们可以将其重写为
n + n(n-1) + n(n-1)(n-2) + ...
嘿！我们知道那个总和——它几乎和我们刚才看到的一样。结果为 Θ(n!)。
综合考虑
总而言之，这个递归算法
- Θ(n!) 的工作仅仅是因为递归调用的次数，每次调用都需要一些基本时间；
- Θ(n!) 递归调用在形成和连接子字符串时完成的工作；和
- Θ(n · n!) 最终递归调用完成的工作，打印出所有排列。
总结这一切给出了您在问题中提出的 Θ(n · n!) 运行时间。
希望对您有所帮助！