java - 以这种方式找到排列的复杂性是什么？

Question

这个方法:

private static void permutation(String prefix, String str)
{
  int n = str.length();
  if(n==0)
    System.out.println(prefix);
  else
  {
    for(int i=0;i<n;i++)
      permutation(prefix+str.charAt(i),str.substring(0,i)+str.substring(i+1,n));
  }
}

查找字符串的所有排列。当使用 permutation("","ABC"); 调用时 它打印:

ABC
ACB
BAC
BCA
CAB
CBA

现在的问题是:这个方法的复杂度是多少？是 O(n!) 还是 O(nlogn)。重复树的答案会很有帮助!谢谢，

Answer 1

都不是:-)

设 T(n,k) 是调用置换所采取的步数，其中 k 是 str 的长度。

显然，T(n, 0) = O(n)。

对于 1 < k <= n，我们执行了 k 次循环体，每次执行一些字符串连接(耗时 O(n))和递归调用耗时 T(n, k-1)。因此，

T(n,k) = k (O(n) + T(n,k-1)). 

猜测这种递归的封闭形式的一种简单方法是写出一些术语:

T(n,k) = k * (n + (k-1) * (n + T(n,k-2)))

让我们分开所有这 n 个术语:

       = kn + k(k-1)n + k(k-1)T(n,k-2)

再扩大一点

       = kn + k(k-1)n + k(k-1)(k-2)n + k(k-1)(k-2)T(n,k-3)

这表明

T(n,k) = kn + k(k-1)n + k(k-1)(k-2)n + ... + k!n
       = n (k + k(k-1) + k(k-1)(k-2) + ... + k!)

和

T(n,n) = n (n + n(n-1) + n(n-1)(n-2) + ... + n!)
       = nn! (1/(n-1)! + 1/(n-2)! + 1/(n-3)! + ... + 1)
             \-----------------   --------------------/
                               \ /
                            1 < x < 2

因此 T(n,n) = O(nn!)