什么是这个算法的复杂度(大O)? [英] What is the complexity (Big-O) of this algorithm?
问题描述
我相当熟悉算法分析,可以告诉大O的大多数算法和我一起工作。但我已经被困了几个小时无法拿出大O此code我写的。
I'm fairly familiar with algorithm analysis and can tell the Big-O of most algorithms I work with. But I've been stuck for hours unable to come up with the Big-O for this code I write.
基本上这是一个方法来产生排列的字符串。它的工作原理是使每个字符的字符串中的第一个字符,并结合其与子的排列小于字符(递归)。
Basically it's a method to generate permutations for a string. It works by making each character in the string the first character and combine it with the permutations of the substring less that character (recursively).
如果我把在code来算的迭代次数,我已经得到了O(N!)和O(N ^ N)之间的事情。但我无法弄清楚如何在精神上对其进行分析。任何的建议是多AP preciated!
If I put in the code to count the number of iterations, I've got something between O(N!) and O(N^N). But I couldn't figure out how to analyse it mentally. Any suggestion is much appreciated!
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:添加计数++
在基本情况下
推荐答案
递推方程: T(N)= N *(!T(N-1)+(N-1)), T(1)= 1
,其中 N = str.length
。
WolframAlfa说,解决办法就是n *(1)<子> N 即 N * N!
。
WolframAlfa says that the solution is n*(1)n i.e., n*n!
.
以上假设所有的字符串操作都是O(1)。否则,如果串子= ...
和 permutations.add(str.charAt(我)+ permOfSub)
行被认为是为O(n),则公式为:
The above assumes that all string operations are O(1). Otherwise if the cost of String sub = ...
and permutations.add(str.charAt(i) + permOfSub)
lines is considered O(n) then the equation is:
T(n+1)=(n+1)*(n + T(n) + n!*(n+1))
T(N)〜(N * N + 2 * N-1)* N!即, O(N!* N * N)
这篇关于什么是这个算法的复杂度(大O)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!