路径复杂性度量研究

软件复杂性度量是对程序静态特性和动态行为的理解难易程度的描述。本文通过分析传统的程序复杂性度量方法的不足之处，提出了一种新的路径复杂性度量方法及计算路径复杂度的算法，并给出了实例。新的度量方法比传统的度量方法更精确和容易实现。     

面向对象程序复杂性度量层次模型

程序复杂性度量可以实现定量地分析程序复杂性，从而为估计成本提供一个标准。为了度量面向对象程序复杂性，在讨论了度量的定义．度量的理论基础后，提出了一种面向对象程序复杂性度量的层次模型。该模型分成5个层次：系统层、类簇层、类继承树层、类层和方法层，每个层次都有自己的度量方法。采用这种分层度量模型的好处是：它是一个框架，各度量方法归属到各层中；各层之间相互独立；一层中方法的修改并不影响其它层。     

程序结构分解及复杂性度量

本文基于程序的结构分解,建立了子流程图、1—入口子流程图、1—入口真子流程图、基本流程图、最大真子流程图、流程图的分解等概念.并给出了程序结构分解的三个定理(定理1,2,3).由此,得到了程序复杂性度量的两个公理及公理化的复杂性度量方法.本文最后的讨论表明经典的度量方法都可化归为本文给出的度量形式.     

消息路径:UML协作图的复杂性度量

针时面向对象软件的复杂性,提出了一种面向UML协作图的软件动态复杂性度量方法--消息路径.基于UML协作图中角色对象间的消息流以及所定义的不同类别的信息标记,给出消息路径图的构造方法和基于消息路径图的面向对象软件动态复杂性度量模型.在该模型中,建立了一组复杂性度量指标,并对这些指标的意义进行了阐述.结合具体实例,给出了消息路径图和各项指标值,并且比较了不同实例的度量结果,表明了所提出度量方法的可行性和实用性.     

基于程序图的McCabe结构复杂性度量

程序复杂性度量是软件工程的一个研究领域 ,不同的软件设计方法可导致不同的程序复杂性。本文讨论了利用程序图进行 Mc Cabe结构复杂性度量的方法。     

信息系统体系结构复杂性度量方法研究*

体系结构技术是进行信息系统设计的重要技术,其复杂性直接决定着建设信息系统的复杂性。研究了程序复杂性的度量方法,在复杂性概念研究的基础上,提出了将体系结构复杂性分为动态复杂性和结构复杂性分开进行度量的方法,并提出基于熵的动态复杂性和结构复杂性评估方法。通过对体系结构复杂性度量方法的研究,可以有效地度量体系结构的复杂性,为项目开发与决策提供有力的依据。     

SSAC,一个基于软件科学法的Ada程序复杂性度量工具

ＳＳＡＣ是一个基于软件科学法的Ａｄａ程序复杂性度量工具，其主要特征是能同时分别度量程序的顺序复杂性和并发复杂性。文中描述了Ａｄａ程序中并发操作符和并发操作元的定义和识别。同时提出在Ａｄａ程序复杂性综合度量中，并发复杂性的加权思想。     

马尔可夫决策过程复杂性的熵测度

应用Shannon熵和其他熵指数来度量马尔可夫决策的复杂性．将马尔可夫链的复杂性、不确定性和不可预测性的度量扩展到马尔可夫决策，提出一套基于信息理论的复杂性度量方法，可用于随机和确定性策略下的完全观测和不完全观测马尔可夫决策．对有关数值进行仿真研究，并给出了计算结果．     

基于继承图的面向对象软件复杂性度量研究

面向对象软件开发是一种新的可以减少成本、提高可用性和灵活性的高效的软件系统开发方法。复杂性度量在软件开发中起着非常重要的作用,它可减少整个开发周期的费用,但目前还没有成熟的用于面向对象软件复杂性的度量方法。文章首先通过继承图描述面向对象软件复杂性度量方法,然后讨论了单元重复继承算法,最后给出了具体实例。     

一种面向对象继承复杂性的综合度量

通过对面向对象系统和当前存在的面向对象度量方法进行分析,提取出与面向对象继承复杂性度量相关的量度。修改并整合这些量度,提出了一种类级继承复杂性和系统级继承复杂性度量方法。经过修改后得出反映继承复杂性的量度有：继承成员个数（NIM）、覆盖成员个数（NOM）、成员名重复数（NRN）、继承路径长度（LIP）、访问方式改变数（NMA）。由此,通过整合可以得到对类级继承复杂性和系统级继承复杂性度量方法。最后,通过与其他度量方法进行比较,说明了该方法对面向对象继承复杂性的度量更为适合。     

Program complexity using Hierarchical Abstract Computers

A model of program complexity is introduced which combines structural control flow measures with data flow measures. This complexity measure is based upon the prime program decomposition of a program written for a Hierarchical Abstract Computer. It is shown that this measure is consistent with the ideas of information hiding and data abstraction. Because this measure is sensitive to the linear form of a program, it can be used to measure different concrete representations of the same algorithm, as in a structured and an unstructured version of the same program. Application of the measure as a model of system complexity is given for “upstream” processes (e.g. specification and design phases) where there is no source program to measure by other techniques.     

New Results on Path Approximation

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.     

A measure of program complexity

We propose a measure of program complexity which takes into account both the relationship between statements and the relationships between statements and data objects (constants and variables). This measure, called program flow complexity, can be calculated from the source text of a program in an easy way.     

一种软件复杂性度量系统的设计与实现

本文结合软件复杂性度量的多种算法,对我们研制开发的一个软件复杂性度量系统,进行了详细介绍,并将系统与已有的各种度量工具进行了分析比较。     

Estimating software testing complexity

ContextComplexity measures provide us some information about software artifacts. A measure of the difficulty of testing a piece of code could be very useful to take control about the test phase.ObjectiveThe aim in this paper is the definition of a new measure of the difficulty for a computer to generate test cases, we call it Branch Coverage Expectation (BCE). We also analyze the most common complexity measures and the most important features of a program. With this analysis we are trying to discover whether there exists a relationship between them and the code coverage of an automatically generated test suite.MethodThe definition of this measure is based on a Markov model of the program. This model is used not only to compute the BCE, but also to provide an estimation of the number of test cases needed to reach a given coverage level in the program. In order to check our proposal, we perform a theoretical validation and we carry out an empirical validation study using 2600 test programs.ResultsThe results show that the previously existing measures are not so useful to estimate the difficulty of testing a program, because they are not highly correlated with the code coverage. Our proposed measure is much more correlated with the code coverage than the existing complexity measures.ConclusionThe high correlation of our measure with the code coverage suggests that the BCE measure is a very promising way of measuring the difficulty to automatically test a program. Our proposed measure is useful for predicting the behavior of an automatic test case generator.     

信息系统体系结构的复杂性分析方法

体系结构设计是信息系统设计中的一个重要环节。体系结构的复杂性是影响系统质量的重要因素。针对信 息系统体系结构设计的特点,定义了系统藕合度和内聚度计算模型;基于藕合度和内聚度评佑结果,提出一种体系结 构复杂度的分析方法。实例证明,该方法是一种有效的复杂性评佑方法。     

Computation of logical effort in high level languages

A new measure of software complexity is introduced, that of logical effort. This measure is an attempt to quantify program complexity by an analysis of the control structure of the program, using the concepts of language virtuality and segment independence. A program is decomposed by the use of these concepts until measurements can be made at the statement level. These measurements, along with measurements of I, the effort necessary to perform a loop, and Q, the effort necessary to determine which branch to take in a decision, are then used to calculate recursively the effort in larger and larger structures, until the program level is reached. An example of this process is given for a short program, along with a brief comparison of the results obtained with a similar measure, that of cyclomatic complexity.

Algorithms for the computation of I and Q are also given, along with examples of their calculation. This process is essentially a decomposition of a Boolean function into disjunctive normal form, followed by a minimization of the form using a weighting measure involving weights on both the operators and the variables in the function.     

A web-based expert system to assess the complexity of manufacturing organizations

Information-theoretic modelling of manufacturing organizations and their supply chains has led to the development of measures of manufacturing complexity. The measures include assessment of the structural, dynamic and decision-making complexity associated with the processing and movement of material and information around a manufacturing system. A computer program has been written to calculate the decision-making complexity of a manufacturing system, under different system layouts and operating characteristics. In order to make the results of this program accessible to manufacturing organizations, an expert system has been developed to act as a mediator between the program and interested organizations. Given some simple quantitative data on manufacturing performance, the expert system can estimate the organization's complexity and suggest some recommendations to reduce it, based on the data provided by the organization. The expert system will be implemented on the web to enable on-line acquisition and searching of data on companies. The quid pro quo of the expert system is that anonymized data on the organizations will be retained so that complexity benchmarks may be established.     

Cyclomatic complexity density and software maintenance productivity

A study of the relationship between the cyclomatic complexity metric (T. McCabe, 1976) and software maintenance productivity, given that a metric that measures complexity should prove to be a useful predictor of maintenance costs, is reported. The cyclomatic complexity metric is a measure of the maximum number of linearly independent circuits in a program control graph. The current research validates previously raised concerns about the metric on a new data set. However, a simple transformation of the metric is investigated whereby the cyclomatic complexity is divided by the size of the system in source statements. thereby determining a complexity density ratio. This complexity density ratio is demonstrated to be a useful predictor of software maintenance productivity on a small pilot sample of maintenance projects