A Complexity Measure

Một Phép đo Độ phức tạp

THOMAS J. McCABE

Chú thích—Bài báo này mô tả một phép đo độ phức tạp theo lý thuyết đồ thị và minh họa cách nó có thể được sử dụng để quản lý và kiểm soát độ phức tạp của chương trình. Trước tiên, bài báo giải thích cách áp dụng các khái niệm lý thuyết đồ thị và đưa ra một giải thích trực quan về các khái niệm đồ thị theo các thuật ngữ lập trình. Các đồ thị điều khiển của một số chương trình Fortran thực tế sau đó được trình bày để minh họa mối tương quan giữa độ phức tạp trực quan và độ phức tạp theo lý thuyết đồ thị. Một số tính chất của độ phức tạp theo lý thuyết đồ thị sau đó được chứng minh, cho thấy, ví dụ, rằng độ phức tạp độc lập với kích thước vật lý (việc thêm hoặc bớt các câu lệnh hàm không làm thay đổi độ phức tạp) và độ phức tạp chỉ phụ thuộc vào cấu trúc quyết định của một chương trình.

Vấn đề sử dụng luồng điều khiển không có cấu trúc cũng được thảo luận. Một đặc trưng của các đồ thị điều khiển không có cấu trúc được đưa ra và một phương pháp đo lường “tính có cấu trúc” của một chương trình được phát triển. Mối quan hệ giữa cấu trúc và khả năng rút gọn được minh họa bằng một số ví dụ.

Phần cuối cùng của bài báo này đề cập đến một phương pháp luận kiểm thử được sử dụng kết hợp với phép đo độ phức tạp; một chiến lược kiểm thử được định nghĩa, trong đó quy định rằng một chương trình có thể đạt được một mức kiểm thử tối thiểu nhất định hoặc chương trình có thể được rút gọn về mặt cấu trúc.

Thuật ngữ chỉ mục—Cơ sở, phép đo độ phức tạp, luồng điều khiển, phân rã, lý thuyết đồ thị, tính độc lập, tuyến tính, mô-đun hóa, lập trình, rút gọn, phần mềm, kiểm thử.

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-2, NO. 4, DECEMBER 1976

A Complexity Measure

THOMAS J. McCABE

Abstract—This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph-theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual Fortran programs are then presented to illustrate the correlation between intuitive complexity and the graph-theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program.

The issue of using nonstructured control flow is also discussed. A characterization of nonstructured control graphs is given and a method of measuring the “structuredness” of a program is developed. The relationship between structure and reducibility is illustrated with several examples.

The last section of this paper deals with a testing methodology used in conjunction with the complexity measure; a testing strategy is defined that dictates that a program can either admit of a certain minimal testing level or the program can be structurally reduced.

Index Terms—Basis, complexity measure, control flow, decomposition, graph theory, independence, linear, modularization, programming, reduction, software, testing.

This section is missing here.

I INTRODUCTION

This section is missing here.

II A COMPLEXITY MEASURE

This section is missing here.

III WORKING EXPERIENCE WITH THE COMPLEXITY MEASURE

This section is missing here.

IV DECOMPOSITION

This section is missing here.

V SIMPLIFICATION

This section is missing here.

VI NONSTRUCTURED PROGRAMMING

This section is missing here.

VII A TESTING METHODOLOGY

This section is missing here.

Appendix