Complexity Measures for Programming Languages.

摘要

A theory of complexity is developed for algorithms implemented in typical programming languages. The complexity of a program may be interpreted in many ways; a method for measuring a specific type of complexity is a complexity measure --some function of the amount of a particular resource used by a program in processing an input. After the complexity of the basic program elements is determined,program complexity is analyzed with respect to single inputs and then with respect to finite sets of legitimate halting inputs. A program equation is developed to aid in the complexity analysis. Using this equation,an input set is partitioned into classes of constant complexity. Several equivalence relations are defined,relating different programs by their complexity. Complexity is also discussed in terms of concatenation and functional equivalence of program. (Author)