A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© Silvester 中级黑马   /  2014-6-30 21:00  /  2187 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 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)

...........................
...........................

依次类推:

代码实现:
  

  1. public class Test {

  2.      public static void main(String[] s) {
  3.           // 定义字符串abcde,字符串越长运行效率越低,用5个测试
  4.           String str = "abcde" ;

  5.           //temp 为辅助空间共享变量
  6.           String temp = new String();

  7.           //调用方法求 abcde 的全排列,
  8.           perm(str, temp);
  9.         }
  10.         
  11.      //递归求取字符串全排列的方法
  12.      public static void perm(String s1, String s2) {
  13.           //循环,依次截取{ri}
  14.           for (int i = 0; i < s1.length(); i++) {        
  15.           //控制{ri}中不能包含已被截取的(R)中的元素               
  16.                if (!(s2.contains(s1.substring(i, i + 1)))) {
  17.                //打印已经求出的perm(X)
  18.                System.out.println(s2 + s1.substring(i, i + 1));
  19.                //递归调用求全排列的方法依次求取剩下的perm(X)
  20.                perm(s1, s2 + s1.substring(i, i + 1));
  21.                }
  22.           }
  23.     }
  24. }
复制代码



时间复杂度分析:  
核心语句为
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)


0 个回复

您需要登录后才可以回帖 登录 | 加入黑马