本帖最后由 Silvester 于 2014-6-30 21:01 编辑
n个元素{r1,r2,…,rn}的全排列算法设计思想。
设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。
R的全排列可归纳定义如下:
当n=1时,perm(R)=(r),其中r是集合R中唯一的元素;
当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。
思想举例:
(a) --> perm (a)
(ab) --> (a) perm (b)
--> (b) perm (a)
(abc) --> (a) perm (b, c)
--> (b, c)
--> (b) perm (c)
--> (c) perm (b)
--> (b) perm (a, c)
--> (a, c)
--> (a) perm (c)
--> (c) perm (a)
--> (c) perm (a, b)
--> (a, b)
--> (a) perm (b)
--> (b) perm (a)
...........................
...........................
依次类推:
代码实现:
- public class Test {
- public static void main(String[] s) {
- // 定义字符串abcde,字符串越长运行效率越低,用5个测试
- String str = "abcde" ;
- //temp 为辅助空间共享变量
- String temp = new String();
- //调用方法求 abcde 的全排列,
- perm(str, temp);
- }
-
- //递归求取字符串全排列的方法
- public static void perm(String s1, String s2) {
- //循环,依次截取{ri}
- for (int i = 0; i < s1.length(); i++) {
- //控制{ri}中不能包含已被截取的(R)中的元素
- if (!(s2.contains(s1.substring(i, i + 1)))) {
- //打印已经求出的perm(X)
- System.out.println(s2 + s1.substring(i, i + 1));
- //递归调用求全排列的方法依次求取剩下的perm(X)
- perm(s1, s2 + s1.substring(i, i + 1));
- }
- }
- }
- }
复制代码
时间复杂度分析:
核心语句为System.out.println(s2 + s1.substring(i, i + 1));
假设初始数据规模为n(即字符串长度为n)
1. 假设初始数据规模为n ,if判断和递归调用语句执行频度为n!次;
2. for循环为程序增加的语句频度后为n次循环;
3. 总的语句执行频度为: O(n * n!),时间复杂度为: T (n!)
[ 注: 时间复杂度与总的语句执行频度程线性关系,即:T(n) = O(f(n)中增长的最快的项/该项系数) ]
空间复杂度分析:
不考虑调用方法时方法区申请分配的空间和递归操作栈的空间
字符串长度(n) + 辅助空间共享变量(n),空间复杂度为:S (2n)
|
|