基于执行序列的程序时间复杂度分析

• 作者: 赵建军 高春风
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 程序分析 静态分析 复杂度分析 循环复杂度 执行序列
• 年，卷（期）: 2011,（8）
• 所属期刊栏目: 软件与算法
• 页码范围: 2716-2720
• 分类号: TP302
• 字数: 5517字
• 语种: 中文

摘要

为了达到更准确、更高效的程序时间复杂度,解决复杂度分析中的循环下的复杂情况,如多个跳出点、嵌套循环和非数值域循环等,提出了基于执行序列计算复杂度的方法.提取出程序方法的各条可能的执行序列及其各条执行序列的相关约束条件和执行效应,在此基础上分析出序列间的关系从而计算出最终的时间复杂度.基于这种方法开发出的工具,通过几个大型的实际程序,发现这种方法可以有效地计算出其中大于90%的方法的运行复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵建军	上海交通大学软件学院	12	35	3.0	5.0
2	高春风	上海交通大学软件学院	1	1	1.0	1.0