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

摘要：

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

关键词：程序分析、静态分析、复杂度分析、循环复杂度、执行序列

所属期刊栏目：32

分类号：TP302(计算技术、计算机技术)

在线出版日期：2011-12-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2716-2720