C语言函数时间复杂度自动计算方法的实现  

IMPLEMENTING AUTOMATIC CALCULATION METHOD OF TIME COMPLEXITY OF C LANGUAGE FUNCTIONS

作　　者：章亦葵[1] 李英第 

机构地区：[1]天津大学软件学院,天津300072 [2]天津大学计算机学院,天津300072

出　　处：《计算机应用与软件》2015年第11期18-22,31,共6页Computer Applications and Software

摘　　要：现有的C语言编译或代码分析软件大多集中于检测C程序代码编码过程的正确性,而对于其代码的时间效率高低无法判定。针对这种情况,通过对标准C语言程序代码语法形式的分析,提出对于C语言函数时间复杂度自动计算的算法原型并加以实现和验证。实验结果表明,C程序代码时间效率的高低很大程度上取决于程序内部函数的时间复杂度。程序中函数整体时间复杂度越高,运行时间效率越低。相比于传统意义上的C代码分析方法,时间复杂度自动计算方法更侧重于对C代码的时间复杂度进行分析和计算,从而可以更快速、准确地对C程序代码时间效率进行判定。Existing C language compilers or code analysis software mostly focus on the correctness detection of C language code compiling process, but have no way to determine the time efficiency level of their codes. In view of this, by analysing the grammatical form of standard C language program code, we presented an algorithm prototype for automatically calculating C language functions time complexity, as well as implemented and validated it. Experimental result shoWed that the time efficiency level of C program code depended greatly on the time complexity of the intrinsic functions of program. The higher the overall time complexity of functions, the lower the run-time efficiency. Compared with C language code analysis method in terms of traditional meaning, this automatic calculation algorithm of time complexity focuses more on analysing and calculating the time complexity of C code, so that it can judge the time efficiency of C program code more quickly and accurately.

关 键 词：C语言 时间复杂度 自动计算 实验 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]