Essential complexity: Difference between revisions

Revision as of 15:33, 28 June 2020

Revision as of 09:23, 17 December 2020

Line 1:

{{About-distinguish2|the numerical measure of a program's "structuredness" defined by McCabe|the notion antonymic to accidental complexity used by Brooks in [[No Silver Bullet]] and subsequent works}}

'''Essential complexity''' is a [[numerical measure]] defined by Thomas J. McCabe, Sr., in his highly cited, 1976 paper better known for introducing [[cyclomatic complexity]]. McCabe defined essential complexity as the cyclomatic complexity of the reduced CFG ([[control flow graph]]) after iteratively replacing (reducing) all [[structured programming]] [[control structure]]s, i.e. those having a single entry point and a single exit point (for example if-then-else and while loops) with placeholder single statements.<ref name="mccabe76">{{cite journal| last=McCabe| date=December 1976| journal=IEEE Transactions on Software Engineering| pages=308–320| title=A Complexity Measure|format=| doi=10.1109/tse.1976.233837}}</ref>{{rp|317}}<ref>http://www.mccabe.com/pdf/mccabe-nist235r.pdf</ref>{{rp|80}}<!-- note that the original paper has an error in the final formula for ev, but this is corrected in the technical report-->

McCabe's reduction process is intended to simulate the conceptual replacement of control structures (and actual statements they contain) with subroutine calls, hence the requirement for the control structures to have a single entry and a single exit point.<ref name="mccabe76"/>{{rp|317}} (Nowadays a process like this would fall under the umbrella term of [[refactoring]].) All structured programs evidently have an essential complexity of 1 as defined by McCabe because they can all be iteratively reduced to a single call to a top-level subroutine.<ref name="mccabe76"/>{{rp|318}} As McCabe explains in his paper, his essential complexity metric was designed to provide a measure of how far off this ideal (of being completely structured) a given program was.<ref name="mccabe76"/>{{rp|317}} Thus greater than 1 essential complexity numbers, which can only be obtained for non-structured programs, indicate that they are further away from the structured programming ideal.<ref name="mccabe76"/>{{rp|317}}