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

Question

Рассмотрим следующий код, чтобы переставить строку, содержащую уникальные символы из Макдауэлл:

Этот код основан на рекурсии, и добавляет к каждому результату путем размещения символа к каждому месту. Если строка содержит n символов, то существует n + 1 таких мест.

Поскольку для каждой строки (существуют n! Возможные строки длины n), вы добавляете n + 1 символов, сложность должна быть 1! + 2! + ... + (n + 1)!

Автор говорит, что сложность O (n!). Это то же самое, что и O (1! + ... + (n + 1)!)? Если да, то почему?

public static ArrayList<String> getPerms(String str){ 
    if (str == null){ 
     return null; 
    } 

    ArrayList<String> permutations = new ArrayList<String>(); 
    if (str.length() == 0){ 
     permutations.add(""); 
     return permutations; 
    } 

    char first = str.charAt(0); 
    String remainder = str.substring(1); 
    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 s, char c, int j){ 
    String start = s.substring(0, j); 
    String end = s.substring(j+1); 
    return start + c + end; 
    } 

Answer 1

Давайте определим F(n) как длина списка, возвращаемого getPerms, когда вы передаёте строку длины n.

При осмотре основного корпуса мы видим, что F(0) == 1.

В рекурсивном случае с длиной строки n > 0, getPerms называет себя рекурсивно на строку длины n-1. Он возвращает список длины F(n-1) (то есть определение F) и сохраняет список в words. Для каждого элемента words он добавляет n элементам к permutations. Таким образом, permutations будет иметь n * F(n-1) элементов, когда он будет возвращен.

Таким образом, F(n) == n * (n-1) * (n-2) * ... * 1 == n!. Функция getPerms возвращает список длины n! с длиной строки n.

Сложность от getPerms? Я предполагаю, что мы говорим о временной сложности. Ну, он выполняет Σ _{i = 0}ⁿ i! (n) для внешнего вызова, плюс (n-1)! для первого рекурсивного вызова, плюс (n-2)! для второго рекурсивного вызова и т. д.). Таким образом, вы можете сказать, что сложность - это O (Σ ⁿ i!) List appends.

Но список приложений не является единственным вычислением здесь. Мы копируем много символов, когда присоединяемся к строкам в Java.

Скажем, G(n) - это количество копий символов, выполненных по вызову getPerms, когда вы передаете строку длиной n.

При осмотре основного корпуса мы видим, что G(0) == 0.

В рекурсивном случае getPerms называет себя на нитке длиной n-1, которая выполняет G(n-1) копии символов и возвращает список F(n-1) строк, каждая длиной n-1. Затем getPerms копирует каждую из этих строк n раз, вставляя другой символ в каждую копию, поэтому F(n-1) * n * n == n * n! символов, скопированных непосредственно в вызове getPerms, в дополнение к G(n-1) из рекурсии.

Таким образом, количество символов, скопированных вызовом getPerms является O (Σ _{я = 0}^п я * I!).