小编ran*_*534的帖子

我的书为函数提供了以下代码，该函数计算一串唯一字符的所有排列（请参见下面的代码），并说运行时间为O（n！），因为存在n！个排列。

我不明白他们如何将运行时间计算为O（n！）。我认为它们的意思是“ n”是原始字符串的长度。我认为运行时间应该类似于O（（n + 1）XY），因为getPerms函数将被调用（n + 1）次，并且X和Y可以表示外部和内部for循环的运行时间分别。有人可以向我解释为什么这是错误的/书的答案是正确的吗？

谢谢。

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); //first character of string
    String remainder = str.substring(1); //remove first character

    ArrayList<String> words = getPerms(remainder);
    for (String word: words)
    {
        for (i = 0; i <= word.length(); i++)
        {
            String s = insertCharAt(word, first, i);
            permutations.add(s)
        }
    }

    return permutations;

}

public static String …