Page 181 - 《软件学报》2026年第5期

2060 软件学报 2026 年第 37 卷第 5 期

骤相对增多, 尽管复杂度随之增加, 但其综合性能得到一定的提升. 下面对本文方法及部分具有代表性的对比方法
就时间复杂度展开分析.

APFD TETC APFD TETC APFD TETC
0.970 0 0.096 0 0.964 0 0.130 0 0.948 0 0.082 0
0.969 7 0.086 5 0.961 9 0.116 2 0.947 4 0.077 2
APFD值 0.969 4 0.077 0 TETC值 APFD值 0.959 8 0.102 4 TETC值 APFD值 0.946 8 0.072 4 TETC值
0.067 6
0.946 2
0.067 5
0.957 7
0.088 6
0.968 8
0.953 5
0.945 0
0.048 5
0.061 0
0.968 5 0.058 0 0.955 6 0.074 8 0.945 6 0.062 8
0.058 0
1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 101112 1 2 3 4 5 6 7 8
迭代次数 迭代次数 迭代次数
(a) Flex 数据集 (b) Tcas 数据集 (c) Schedule2 数据集
APFD TETC APFD TETC APFD TETC
0.962 0 0.210 0 0.954 0 0.260 0 0.97 19.425
0.955 2 0.203 2 0.952 4 0.240 8 0.96 17.425
APFD值 0.948 4 0.196 4 TETC值 APFD值 0.950 8 0.221 6 TETC值 APFD值 0.95 15.425 TETC值
13.425
0.202 4
0.941 6
0.949 2
0.94
0.189 6
0.934 8
0.92
9.425
0.176 0
0.946 0
0.928 0 0.182 8 0.947 6 0.183 2 0.93 11.425
0.164 0
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9101112131415
迭代次数 迭代次数 迭代次数
(d) Jsoup 数据集 (e) Jacksoncore 数据集 (f) Camel-core 数据集
图 4 不同数据集中迭代次数的影响

1) 就本文方法 TPG-TCP 而言, 其时间复杂度主要体现在粗粒度用例分组与细粒度用例分组排序两个部分. 粗粒
2
度用例分组的时间复杂度为 O(N M), 其中 N 为测试用例数, M 为覆盖元素的数量; 在细粒度用例分组排序的单轮迭
代中, 更新用例-语句数表 TC 的次数等于语句标记表 S co 中的元素个数, 时间复杂度为 O(NM). 可知, 细粒度用例分
v
组排序的时间复杂度大致为 O(NMI), I 是迭代次数. 由于 N 通常大于 I, 因此 TPG-TCP 的时间复杂度大致为 O(N M).
2
2) 就对比方法 AGA (较新的基于贪心策略的方法, 在对比方法中的排序效率最优, 与本文结构最为相似) 来
说, 它的时间主要消耗在每次选择测试用例后的更新操作中, 时间复杂度大致为 O(NMI). 与方法 AGA 相比, TPG-
TCP 的复杂度虽有所增加, 但 AGA 仅专注于效率的提升, 并未提高 Additional 策略的有效性, 而 TPG-TCP 在提高
效率的同时也对排序策略进行了改进, 提升了排序的有效性.
3) 就对比方法 WOA-TCP (较新的基于群智能算法的方法, 与本文方法同为启发式算法) 来说, 它的时间主要消
耗在搜索最优种群个体过程, 时间复杂度大致为 O(PNI), 其中 P 为种群规模, 迭代次数 I 通常为 1 000. 该方法将
TCP 视为 NP-hard 问题, 利用鲸鱼优化算法在用例序列的全排列中搜索最优解, 牺牲了时间复杂度, 但换取了一定的
有效性. TPG-TCP 的复杂度与 WOA-TCP 方法相近, 但通过对比实验可知其在整体性能上优于 WOA-TCP 方法.
4) 就对比方法 FB-TCP (最新的基于故障的方法, 与本文方法同采用集成策略) 来说, 它的时间主要消耗在利
用各个子方法生成用例序列, 并交换各序列中存在冲突的用例排名以生成最终优先级序列的过程, 时间复杂度大
3
2
致为 O(N F) + O(NF) + O(N F) + O(N(N + F)) + O(2 ), 即 O(N F), 其中 F 为故障数, C 为冲突的测试用例对, 最大
C
3
值为 20. 该方法采用 3 种集成方式对 4 种基于故障方法的结果进行组合排序, 兼顾了排序过程的多种因素, 排序
有效性较高, 但在效率上表现较差. TPG-TCP 的复杂度会高于 FB-TCP 方法, 且通过对比实验得知, 在整体性能上
也会优于 FB-TCP 方法.
5) 就对比方法 KS-TCP (最新的基于机器学习的方法, 与本文结构较为相似) 来说, 它的时间主要消耗在聚类
2
测试用例的过程, 时间复杂度为 O(NM /K), K 为簇的个数. 该方法利用 K-medoids 聚类挖掘用例间的相似性, 在用
例相似度计算上耗费了大量时间. 由于通常 M > N > K, 故 TPG-TCP 在大多数情况下的复杂度低于 KS-TCP. 另
外, 通过对比实验得知, TPG-TCP 在整体性能上相较于 KS-TCP 方法也有所提升.
综上分析可知, 各方法的时间复杂度大小关系为 FB-TCP (或 KS-TCP) > TPG-TCP (或 WOA-TCP) > AGA. 尽
管从时间复杂度上来看, 本文方法 TPG-TCP 高于 AGA, 但就排序性能而言, 本文方法更优, 相较于 AGA, 所提方
法在 APFD、TETC 指标上分别最少提升 1.06% 和 4.06%. 相较于 WOA-TCP、FB-TCP 与 KS-TCP 方法, 所提方
法 TPG-TCP 的时间复杂度相近或更低, 排序性能均更佳, 在 APFD 指标上分别最少提升 1.63%、1.40% 和 4.19%,