复杂生成的字符串

Question

我试图找出的代码复杂度（从破解编码面试书），用于产生一个给定的字符串的所有排列如何为O的排列（N！）。

我知道这是最好的复杂性，因为我们有n！排列，但我想了解它codewise，因为不是每个算法，这将是O（n！）。

验证码：

import java.util.*; 

public class QuestionA { 

    public static ArrayList<String> getPerms(String str) { 
     if (str == null) { 
      return null; 
     } 
     ArrayList<String> permutations = new ArrayList<String>(); 
     if (str.length() == 0) { // base case 
      permutations.add(""); 
      return permutations; 
     } 

     char first = str.charAt(0); // get the first character 
     String remainder = str.substring(1); // remove the first character 
     ArrayList<String> words = getPerms(remainder); 
     for (String word : words) { 
      for (int j = 0; j <= word.length(); j++) { 
       String s = insertCharAt(word, first, j); 
       permutations.add(s); 
      } 
     } 
     return permutations; 
    } 

    public static String insertCharAt(String word, char c, int i) { 
     String start = word.substring(0, i); 
     String end = word.substring(i); 
     return start + c + end; 
    } 

    public static void main(String[] args) { 
     ArrayList<String> list = getPerms("abcde"); 
     System.out.println("There are " + list.size() + " permutations."); 
     for (String s : list) { 
      System.out.println(s); 
     } 
    } 

} 

这是我想到现在直到： 在任何函数调用，获得的单词数为（n-1）;假设我们在一个剩余长度为（n-1）的地方。现在为所有这些（n-1）个字在所有可能的位置插入第n个元素需要（n-1）*（n-1）个时间。

所以跨越执行，它应是第（n-1）^ 2 +（N-2）^ 2 +（N-3）^ 2 + ... 2^2点+ 1^2点的操作，这我不认为是！

我在这里错过了什么？

Answer 1

我认为getPerms的时间复杂度为O((n + 1)!)。

我们用T(n)表示getPerms的运行时间，其中n是输入的长度。

============================================== =====================

这两个if分支和行char first = str.charAt(0)需要O(1)时间。而下面的行需要O(n)时间：

String remainder = str.substring(1); // remove the first character 

下一行需要时间T(n - 1)：

ArrayList<String> words = getPerms(remainder); 

现在我们考虑嵌套for-loops的运行时间。外for-loop的大小是(n-1)!：

for (String word : words) { 

和内for-loop的大小为n + 1：

for (int j = 0; j <= word.length(); j++) { 

和的insertCharAt复杂性也是O(n)。

所以嵌套for-loops的总运行时间为(n + 1) * (n - 1)! * O(n) = O((n + 1)!)。

因此，我们有如下关系：

 
T(n) = T(n - 1) + O(n) + O((n + 1)!) 
    = T(n - 1) + O(n) + O((n + 1)!) 
    = (T(n - 2) + O(n - 1) + O(n!) + O(n) + O((n + 1)!) 
    = T(n - 2) + (O(n - 1) + O(n)) + (O(n!) + O((n + 1)!)) 
    = ... 
    = O(n2) + (1 + ... + O(n!) + O((n + 1)!)) 
    = O((n + 1)!) 

Answer 2

如果你正在学习这一点，这将是更好地学习一般的解决方案，而不是仅仅在你的例子提出的实现。 Sedgewick做了我所知道的最好的分析。我在班上教它。

https://www.cs.princeton.edu/~rs/talks/perms.pdf

的生成函数的每个调用的复杂性为O（n）。因此成本是O（n！）。

您提供的代码效率极低。有一个巨大的恒定因素，因为您正在创建大量的字符串对象和数组，这是您在Java中可以做的最无效率的事情之一。

如果您只是想要遍历所有排列，请排列单个实体，不要生成列表。这里是一个更快的实现：

public class Permute { 
    private int[] a; 
    private void swap(int i, int j) { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 
    public Permute(int n) { 
     a = new int[n]; 
     for (int i = 0; i < n; i++) 
      a[i] = i+1; 
     this.generate(n); 
    } 
    public void generate(int N) { 
     //  System.out.println("generate(" + N + ")"); 
     if (N == 0) doit(); 
     for (int c = 0; c < N; c++) { 
      //   System.out.print("Swapping: " + c + "," + N); 
      swap(c, N-1);       //swap(0, 7) 
      generate(N-1); 
      //   System.out.print("Swapping: " + c + "," + N); 
      swap(c, N-1); 
     } 
    } 
    public void doit() { 
     for (int i = 0; i < a.length; i++) 
      System.out.print(a[i] + " "); 
     System.out.println(); 
    } 

    public static void main(String[] args) { 
     Permute p = new Permute(4); 
    } 
} 

是塞奇威克显示另一种方法是堆，也就是每置换只有一个交换，而不是2.这是一个C++实现：

#include <vector> 
#include <iostream> 

using namespace std; 
class Heaps { 
private: 
    vector<int> p; 
public: 
    Heaps(int n) { 
     p.reserve(n); 
     for (int i = 0; i < n; i++) 
      p.push_back(i+1); 
     generate(n); 
    } 
    void doit() { 
     cout << "doit size=" << p.size() << '\n'; 
     for (int i = 0; i < p.size(); i++) 
      cout << p[i]; 
     cout << '\n'; 
    } 
    void generate(int N) { 
     //  cout << "generate(" << N << ")\n"; 
    if (N == 0) 
      doit(); 
    for (int c = 0; c < N; c++) { 
      generate(N-1); 
      swap(p[N % 2 != 0 ? 0 : c], p[N-1]); 
     } 
    } 
}; 


int main() { 
    Heaps p(4); 
}