递归字符串置换函数的复杂性
递归字符串置换函数的复杂性
提问于 2011-03-20 01:28:53
来自：Are there any better methods to do permutation of string?
这个函数的复杂度是多少？
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);
}
}
}回答 3
Stack Overflow用户
回答已采纳
发布于 2011-03-20 03:51:39
忽略打印，满足的递归关系为
T(n) = n*T(n-1) + O(n)
如果使用G(n) = T(n)/n!，我们会得到
G(n) = G(n-1) + O(1/(n-1)!)
这就给了G(n) = Theta(1)。
因此，T(n) = Theta(n!)。
假设打印恰好发生在n!次，我们得到时间复杂度为
Theta(n * n!)
Stack Overflow用户
发布于 2011-03-20 02:29:18
在不深入研究代码的情况下，我想我可以很有把握地说，它的复杂度是O(n!)。这是因为枚举n个不同元素的所有排列的任何有效过程都必须遍历每个排列。有n个！排列，所以算法必须至少是O(n!)。
编辑：
这实际上是O(n*n!)。感谢@templatetypedef指出这一点。
Stack Overflow用户
发布于 2011-03-20 01:37:30
long long O(int n)
{
if (n == 0)
return 1;
else
return 2 + n * O(n-1);
}
int main()
{
//do something
O(end - mid);
}这将计算算法的复杂度。
实际上O(N)是N!!! = 1 * 3 * 6 * ... * 3N
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5363619
复制相关文章
相似问题