java - 生成字符串排列的复杂性

Question

我想弄清楚用于生成给定字符串的所有排列的代码(来自 Cracking the Coding Interview 一书)的复杂度是 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!。

我在这里错过了什么？

Answer 1

我认为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)!)