算法打印字符串的排列 - 运行时间分析

我有下面的代码来打印指定字符串的排列。 [为了简化和不丢失专注于什么，我想，让我们假设有没有字符串中的字符复制]算法打印字符串的排列 - 运行时间分析

public static int count = 0; 

public static void permute(String soFar, String strLeft) { 

    if(strLeft.length() == 1) { 
     soFar += strLeft; 
     System.out.println(++count + " :: " + soFar); 
    } 

    for(int i=0; i<strLeft.length(); i++) { 
     permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1)); 
    } 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    String input = "abcd"; 
    permute("",input); 
}

我想弄清楚这个代码的运行时间。

我至今思念链：想写一个复发，

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

有n个！排列，但递归调用的次数大于n !.实际上，对于输入字符串为“abcd”的例子，即4个字符，排列函数的调用次数为65.

任何关于如何查找此代码的运行时间的指针？

来源

2013-03-05 Anurag Kapur

什么是更大 - 电话给该方法的数字或数字的，它将其运行时的输出量？ – Makoto 2013-03-05 02:15:34

重复/类似的问题？ http://stackoverflow.com/questions/11425344/what-is-the-complexity-big-o-of-this-algorithm – apnorton 2013-03-05 02:16:27

@anorton - 是的，这看起来像一个重复。谢谢！我正在通过另一个线程的答案，并将其标记为已关闭。 – 2013-03-05 02:18:01

嗯，首先，你让多余的电话。如果只剩下一个字符，则会发出解决方案。但是，你仍然会用空字符串调用permute并破坏调用计数。

我的第一个改进是一个else添加到if条款。

public static void permute(String soFar, String strLeft) { 

    if(strLeft.length() == 1) { 
     soFar += strLeft; 
     System.out.println(++count + " :: " + soFar); 
    } 
    else { 
     for(int i=0; i<strLeft.length(); i++) { 
      permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1)); 
     } 
    } 
}

这减少了41的调用数量。并计算调用次数，构造调用树并统计节点。当每个呼叫由从字符串去除一个字符进行，则有：
1通话长度为4的，长度为3的
4呼叫，长度为2的
12呼叫和长度为1的
24呼叫

其中总计为41.Voilá。

来源

2013-03-05 07:43:09 alzaimar

谢谢。因此，一个大小为n的问题的一般解决方案是：n！/ 1！ + n！/ 2！ + ... + n！/ n！ – 2013-03-06 02:36:45

我仍然不知道如何将上面的一般解决方案转换成相应的Big-Oh，但是对于我来说理解一个表示问题或递归调用如何扩散的关系更重要。所以，对你的答案+1，我已标记为接受。谢谢！ – 2013-03-06 02:38:38

不客气。 – alzaimar 2013-03-06 10:33:11

算法打印字符串的排列 - 运行时间分析

回答

相关问题