0

这是一个简单的程序，可以找到给定字符串的所有排列：

void perm( char str[], int len )
{
if ( len == 1 )
   cout << str << endl ;
else
    for ( int i=0; i<len; i++ ) {
        swap( str[len-1], str[i] ) ;
        perm( str, len-1 ) ;
        swap( str[len-1], str[i] ) ;
    }
}

这个函数的 T(n) 是多少？如何计算此函数的 Big Oh（或 Theta）？

4

3 回答 3

2

For循环执行n递归，到n*T(n-1)，加上O(n)，因为你还需要交换2n次，所以

T(n) = n*T(n-1)+O(n)

n = 5 for sake of my keyboard

T(n) = n*T(n-1) + n  
T(n) = n*[(n-1)*T(n-2) + (n-1)] + n  
T(n) = n*[(n-1)*[(n-2)*T(n-3) + (n-2)] + (n+1)] + n  
T(n) = n*[(n-1)*[(n-2)*[(n-3)*T(n-4) + (n-3)] + (n-2)] + (n-1)] + n  
T(n-4) = 1 ----------------------^  
Simplify 
T(n) = n*[(n-1)*[(n-2)*[(n-3) + (n-3)] + (n-2)] + (n-1)] + n  
T(n) = n*[(n-1)*[(n-2)*[2(n-3)] + (n-2)] + (n-1)] + n  
T(n) = n(n-1)(n-2)*(n-3)*2 + (n-1)(n-2) + n(n-1) + n  
T(n) = n! + O(n*n!)    <--  wrong, see comment for right answer
T(n) = O(n*n!)    <--  wrong, see comment for right answer

你看到模式

于 2012-08-28T18:54:38.223 回答
2

设初始输入字符串的长度为 N。

假设调用 perm(str (size = N), len=i) 所花费的时间为 T(i)

T(1) = N

和

T(i > 1) = iT(i-1) + i

则总时间为 T(N)，

要计算此重复的封闭形式，请参见此处：

https://math.stackexchange.com/questions/188119/closed-form-for-t1-k-tx-xtx-1-x

答案是：

T(N) is approximately (N + e - 1)N!

因此，当 N 接近无穷大时，函数的性能为：

O((N + e - 1)N!) = O(N(N!))
于 2012-08-28T19:30:57.223 回答
1

N个项目的可能排列数是N！（阶乘），并且此代码似乎使用它输出的每个排列的 O(1) 操作。因此，建设成本为 O(N!)，相当于 O(N^N)。

或者可能是 O(N!*N)，因为对于每个排列，N 项都会打印到控制台。

于 2012-08-28T18:35:58.273 回答