Сложность для генерации перестановок строки

Я пытаюсь выяснить, как сложность кода (от взлома книги Интервью кодирования) для генерации всех перестановок данной строки равна 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-й элемент во все возможные места для всех этих (n-1) слов, требуется(n-1)*(n-1) Время.

Таким образом, через выполнение, это должно быть (n-1)^2+(n-2)^2+(n-3)^2+....2^2+1^2 операции, которые я не думаю, что n!.

Что я пропустил здесь?

2 3
algorithm time-complexity permutation

2 ответа:

Я думаю, что временная сложность getPerms равна O((n + 1)!).

Обозначим время работы getPerms через T(n), где 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)!)
1

Если вы изучаете это, было бы лучше изучить общие решения, а не только реализацию, представленную в вашем примере. Седжвик сделал лучший анализ, который я знаю. Я преподаю его в своем классе.

Https://www.cs.princeton.edu/~РС/переговоры/завивка.формат 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);
    }
}
Другой метод, который показывает Седжвик, - это Heaps, который представляет собой только один своп на перестановку вместо 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);
}
1