我非常熟悉算法分析,可以说出我使用的大多数算法中的Big-O。但我已经被困了好几个小时,无法为我写的代码想出Big-O。
基本上,这是一种为字符串生成排列的方法。它的工作原理是将字符串中的每个字符作为第一个字符,并将其与减去该字符的子字符串的排列组合(递归)。
如果我输入代码来计算迭代次数,那么我得到了介于O(N!)和O(N^N)之间的值。但我不知道如何在心理上分析它。非常感谢您的任何建议!
import java.util.ArrayList;
import java.util.List;
public class Permutation {
int count = 0;
List<String> findPermutations(String str) {
List<String> permutations = new ArrayList<String>();
if (str.length() <= 1) {
count++;
permutations.add(str);
return permutations;
}
for (int i = 0; i < str.length(); i++) {
String sub = str.substring(0, i) + str.substring(i + 1);
for (String permOfSub : findPermutations(sub)) {
count++;
permutations.add(str.charAt(i) + permOfSub);
}
}
return permutations;
}
public static void main(String[] args) {
for (String s : new String[] {"a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh"}) {
Permutation p = new Permutation();
p.findPermutations(s);
System.out.printf("Count %d vs N! %d%n", p.count, fact(s.length()));
}
}
private static int fact(int i) {
return i <= 1 ? i : i * fact(i-1);
}
}
编辑1:添加测试程序
编辑2:在基本情况中添加count++
递推方程:T(n) = n*(T(n-1) + (n-1)!), T(1) = 1
,其中n = str.length
。
WolframAlfa说,解是n*(1)n,即n*n!
。
以上假设所有字符串操作都是O(1)。否则,如果String sub = ...
和permutations.add(str.charAt(i) + permOfSub)
线路的成本被认为是O(n),则方程为:
T(n+1)=(n+1)*(n + T(n) + n!*(n+1))
T(n)~(n*n+2*n-1)*n!即O(n!*n*n)