一类新型组合数字序 列的快速生成算法
报告人：杨忠昊 云南大学软件学院 2015 年 10 月 23 日
目录
1. 相关背景介绍 2. 算法及相关模型 3. 结果比较 4. 结论
相关背景 介绍
组合计算
算法及相关模型 算法及相关模型
穷举算法
1、对于一个N长的0-1向量，首先计数其中1的个数，记为p 2、从高位向低位扫描其中的的01的个数，需注意，当扫描到最低 位时，最低位和最高位组成一个块进行判断。统计结果记为q 3、穷举0-1向量，统计数p，q相同的结果数目。
耗时结果对比
N 2 5 8 10 12 14 16 18 20 22 24 26
耗时对比-单位 秒
本文方法 穷举法 加速比
1.81E-05 2.22E-05 4.02E-05 5.79E-05 7.96E-05 0.0001129 0.000148618 0.000197883 0.00026316 0.000341574 0.000444211 0.000576817
对数耗时对比
1.00E+02
1.00E&#算时间)
1.00E+00 1.00E-01 1 2 3 4 5 6 7 8 9 10111213141516171819202122232425 1.00E-02 1.00E-03 1.00E-04 1.00E-05
0-1向量长度
本文方法 穷举方法 本文方法
谢谢
源代码地址：https:///housejar/Variant-Logic.git
1.00E+05 1.00E+04 1.00E+03 1.00E+02
1.00E+01
1.00E+00 2 4 6 8 10 12 14 16 18 20 22 24 26 28
0-1向量长度
0-1向量长度
结论
从运行时间测量结果可以看出变值三项式计算 方法较穷举算法有本质的飞跃 利用多项式时间复杂性完成了原来需要利用指 数增长时间复杂性的计算问题 从加速比按对数比较曲线的直线增长，表示随 着N的增加大而加速比以指数增长
初始化一个 0-1向 量 否
计数 p， q
1 1010111111111110
N=16，p=13，q=3
统计 p，q相同的向 量数目
穷举结束 ?
是 输出结果
算法及相关模型 算法及相关模型
产生式三角数算法
产生式三角数计算
传递参数 产生式三角数 N，p，{q} 值计算
输入参数N，p
qRange计算
输出产生式三角数序列
28
0.000667137
1663.045548
2.49E+06
结果比对
耗时对比
1.80E+03 1.60E+03 1.40E+03 1.20E+03 1.00E+03 8.00E+02 6.00E+02 4.00E+02 2.00E+02 0.00E+00 1 3 5 7 9 11 13 15 17 19 21 23 25 27 1.00E+03
5.67E-05 3.05E-04 0.002703856 0.012553674 0.030896045 0.057432914 0.262606532 1.121838129 5.033695147 21.09830564 89.92283789 391.6250866
3.14E+00 1.38E+01 6.72E+01 2.17E+02 3.88E+02 5.09E+02 1.77E+03 5.67E+03 1.91E+04 6.18E+04 2.02E+05 6.79E+05
0-1向量长度
穷举方法
加速比增长曲线
3.00E+06 2.50E+06 1.00E+07 1.00E+06
对数加速比增长曲线
lg(原加速比)
2 4 6 8 10 12 14 16 18 20 22 24 26 28
加速比
2.00E+06 1.50E+06 1.00E+06 5.00E+05 0.00E+00