生成字符串排列的复杂度

Question

我正在尝试弄清楚一个生成给定字符串所有排列的代码（来自《破解面试官》一书）的复杂度为O(n!)。

我知道这是最佳可能的复杂度，因为我们有n！个排列，但我想理解代码方式，因为并非每个执行此操作的算法都是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次操作，我认为这不是n!。

我错在哪里了？

- nikel

---

我不知道我是否正确，但我认为它是O((N+1)!)？ - shole

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循环的运行时间。外部for循环的大小为(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)!)

- chiwangc

---

@给出负评者，请解释一下你的负评原因，这样我才能改进我的回答。 - chiwangc

Answer 2

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

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

每次调用 generate 函数的复杂度为 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);
    }
}

另一种Sedgewick展示的方法是堆，每个排列只需要进行一次交换而不是两次。以下是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);
}

- Dov