运行置换函数的时间

Question

我的书为计算一串唯一字符的所有排列的函数提供了以下代码（见下面的代码），并说运行时间是 O(n!)，"since there are n! permutations."

我不明白他们如何将运行时间计算为 O(n!)。我假设他们的意思是 "n" 是原始字符串的长度。我认为运行时间应该是 O((n + 1)XY)，因为 getPerms 函数将被调用 (n + 1) 次，而 X 和 Y 可以表示运行分别是外循环和内循环的时间。有人可以向我解释为什么这是错误的/这本书的答案是正确的吗？

谢谢。

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 insertCharAt(String word, char c, int j)
{
    String start = word.substring(0, i);
    String end = word.substring(i); 
    return start + c + end;
}

资料来源：破解编码面试

Answer 1

N个元素的排列数为N * (N - 1) * (N - 2) * ... * 2 * 1，即N!.

第一个字符可以是 N 个字符中的任意一个。下一个字符可以是剩余的 N - 1 个字符之一。现在我们已经有 N * (N - 1) 个可能的案例。

因此，继续我们将在每个步骤中处理 N * (N - 1) * (N - 2) * ... 个案例。

因为 N 元素的排列数是 N!，所以没有一个实现可以比 N! 更快地排列长度 N 的数组。

Answer 2

根据我们的直觉，很明显没有现有算法生成 N 个项目的排列，其性能优于 O(n!)，因为有 n！可能性。

您可以将递归代码简化为递归方程，因为 gePerm(n) 其中 n 是长度为 n 的字符串将调用 getPerm(n-1)。然后，我们使用它的所有值 returns 并放置一个循环 N 次的内部循环。所以我们有

P_n = nP_n-1
P₁ = 1

很容易看出P_n = n！通过伸缩方程。

如果你很难想象我们是如何得出这个等式的，你也可以这样想

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

运行置换函数的时间

Running time of permutation function

java

algorithm

recursion

performance

permutation

运行 置换函数的时间

Running time of permutation function

java

algorithm

recursion

performance

permutation

运行置换函数的时间