string 递归字符串置换函数的复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5363619/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
complexity of recursive string permutation function
提问by rajya vardhan
From: Are there any better methods to do permutation of string?
what is the complexity of this function???
这个函数的复杂度是多少？？？
void permute(string elems, int mid, int end)
{
static int count;
if (mid == end) {
cout << ++count << " : " << elems << endl;
return ;
}
else {
for (int i = mid; i <= end; i++) {
swap(elems, mid, i);
permute(elems, mid + 1, end);
swap(elems, mid, i);
}
}
}
回答by
Ignoring the print, the recurrence relation satisfied is
忽略打印，满足的递推关系为
T(n) = n*T(n-1) + O(n)
T(n) = n*T(n-1) + O(n)
If G(n) = T(n)/n!we get
如果G(n) = T(n)/n!我们得到
G(n) = G(n-1) + O(1/(n-1)!)
G(n) = G(n-1) + O(1/(n-1)!)
which gives G(n) = Theta(1).
这给G(n) = Theta(1).
Thus T(n) = Theta(n!).
因此T(n) = Theta(n!)。
Assuming that the print happens exactly n!times, we get the time complexity as
假设打印恰好发生n!次数，我们得到时间复杂度为
Theta(n * n!)
Theta(n * n!)
回答by MAK
Without looking too deeply at your code, I think I can say with reasonable confidence that its complexity is O(n!). This is because any efficient procedure to enumerate all permutations of n distinct elements will have to iterate over each permutation. There are n! permutations, so the algorithm has to be at least O(n!).
无需太深入地查看您的代码，我想我可以有合理的信心说它的复杂性是 O(n!)。这是因为枚举 n 不同元素的所有排列的任何有效过程都必须迭代每个排列。有n个！排列，因此算法必须至少为 O(n!)。
Edit:
编辑：
This is actually O(n*n!). Thanks to @templatetypedef for pointing this out.
这实际上是 O(n*n!)。感谢@templatetypedef 指出这一点。
回答by Mihran Hovsepyan
long long O(int n)
{
if (n == 0)
return 1;
else
return 2 + n * O(n-1);
}
int main()
{
//do something
O(end - mid);
}
This will calculate complexity of the algorithm.
这将计算算法的复杂度。
Actualy O(N) is N!!! = 1 * 3 * 6 * ... * 3N
实际上 O(N) 是 N!!! = 1 * 3 * 6 * ... * 3N
