0

我想知道以下算法的大哦

public List<String> getPermutations(String s){
    if(s.length()==1){
        List<String> base = new ArrayList<String>();
        base.add(String.valueOf(s.charAt(0)));
        return base;
    }

    List<String> combos = createPermsForCurrentChar(s.charAt(0),
                                    getPermutations(s.substring(1));

    return combos;
}
 private List<String> createPermsForCurrentChar(char a,List<String> temp){
    List<String> results = new ArrayList<String>();
    for(String tempStr : temp){
        for(int i=0;i<tempStr.length();i++){
            String prefix = tempStr.substring(0, i);


            String suffix = tempStr.substring(i);

            results.add(prefix + a + suffix);
        }


    }
    return results;
}

这就是我认为的 getPermutations 被称为 n 次，其中 n 是字符串的长度。我的理解是 createPermutations 是 O(l * m) 其中 l 是列表 temp 的长度，m 是 temp 中每个字符串的长度。

但是，由于我们正在查看最坏情况分析，因此 m<=n 和 l<= n!。在每次递归调用中，临时列表的长度都会不断增长，temp 中每个字符串中的字符数也会不断增长。

这是否意味着这个算法的时间复杂度是O(n * n! *n)。还是 O(n * n * n) ？

4

2 回答 2

2

好吧，我将把它写下来作为答案，而不是一长串评论。

将 getPerm 在长度为 n 的字符串上的运行时间表示为 T(n)。观察getPerm里面，它调用了getPerm(string length n-1)，很清楚

T(n)=T(n-1) + [run time of createPerm]

请注意，createPerm 有 2 个嵌套循环。外部循环遍历 getperm（长度为 n-1 的字符串）的结果大小，内部循环遍历 n-1（单个字符串的长度）。getPerm(string of length n-1) 的结果是 T(n-1) 个字符串的列表。由此，我们得到

[run time of createPerm] = (n-1) T(n-1)

将其代入前面的等式给出

T(n) = T(n-1) + (n-1) T(n-1) = n T(n-1)

T(1) = 1 从退出条件。我们可以扩展来找到解决方案（或者，或者，使用 Z 变换：无法计算出这种递归的复杂性）。由于它是一个简单的方程，因此展开速度更快：

 T(n) = n T(n-1)
      = n (n-1) T(n-2)
      = n (n-1) (n-2) T(n-3) ....
      = n (n-1) ... 1
      = n!

所以 T(n) = n!

练习：通过归纳证明这一点！:p

这有意义吗？让我们考虑一下。我们正在创建 n 个字符的排列：http ://en.wikipedia.org/wiki/Permutation 。

编辑：注意 T(n)=n! 是 O(n!)

于 2013-01-30T16:20:34.987 回答
1

我不是最好的组合学，但我认为它是 O(n^3) 其中 n 是字符串中的字符数。

我的逻辑是这样的：

getPermutations(String)

被调用与调用有关：

createPermsForCurrentChar(s.charAt(0),getPermutations(s.substring(1));

在第一次调用中，您传递参数 (charAt(0)，长度为 s.length-1 的子字符串)，然后 (charAt(1)，长度为 s.length-2) 的子字符串 ... 用于 O(n) 调用。

更重要的是每次我们输入 createPermsForCurrentChar 时 List temp 中的元素数。

首先，让我们将函数作为一个独立的东西来分析：假设 中有 k 个元素List<String> temp，它们的长度单调递增，用 L=当前长度表示，从 L=1 开始，以 L=k 结束。

外部for循环将迭代k次，这很容易。内部 for 循环将迭代 L 次。我们的复杂度是 O(k"L")。L 用引号引起来是因为它每次都变，我们看看它长什么样子： 第一次外循环迭代，内循环执行一次。第二次外循环迭代，内循环执行两次，依此类推，直到内循环执行 k 次，得到 1+2+3+4+...k = O(k^2)。

所以 createPermsForCurrentChar 是 O(k^2) 复杂度，其中 k 是元素的数量List<String> temp（也是 temp 中最长字符串的大小）。我们现在想知道的是——List<string> temp每次调用有多少元素？

当我们最终在递归中达到基本情况时，我们将字符串的倒数第二个字符和字符串的最后一个字符传递给 createPermsForCurrentChar，因此 k=1。它将创建一个长度为 O(k) 的字符串。这允许下一次执行从堆栈中弹出并再次调用 createPermsForCurrentChar，这次 k=2。然后 k=3、k=4、k=5 等。

我们知道由于我们的递归关系，createPermsForCurrentChar 被调用了 O(n) 次，所以 k 最终将 = n。(1 + 2 + 3 + ... + n) = O(n^2)。考虑到 createPermsForCurrentChar 的复杂性，我们得到 (1^2 + 2^2 + 3^2 + ... n^2) = (1/3)n^3 + (1/2)n^2 + ( 1/6)n (来自http://math2.org/math/expansion/power.htm )。

由于我们只关心我们的主导值，我们可以说算法是 O(n^3)。

于 2013-01-29T17:01:15.363 回答