Programming complexity: Difference between revisions

Revision as of 11:29, 24 May 2018

Latest revision as of 15:37, 21 June 2025

(16 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Attribute of a software system}}

{{Distinguish|Computational complexity theory}}'''Programming complexity''' (or '''software complexity''') is a term that encompassesincludes numeroussoftware properties of a piece of software, all of whichthat affect internal interactions. According to severalSeveral commentators, there is a distinctiondistinguish between the terms "complex" and "complicated". Complicated implies being difficult to understand, but with time and effort, ultimately knowable. Complex, onby the other handcontrast, describes the interactions between a number of entities. As the number of entities increases, the number of interactions between them would increaseincreases exponentially, andmaking it would get to a point where it would be impossible to know and understand them all of them. Similarly, higher levels of complexity in software increase the risk of unintentionally interfering with interactions, andthus so increasesincreasing the chancerisk of introducing defects when makingchanging changesthe software. In more extreme cases, it can make modifying the software virtually impossible. The idea of linking software complexity to the maintainability of the software has been explored extensively by [[Meir M. Lehman|Professor Manny Lehman]], who developed his [[Lehman's laws of software evolution|Laws of Software Evolution]] from his research. He and his co-Author [[Les Belady]] explored numerous possible [[Software metrics|Software Metrics]] in their oft cited book,<ref>MM Lehmam LA Belady; Program Evolution - Processes of Software Change 1985</ref> that could be used to measure the state of the software, eventually reaching the conclusion that the only practical solution would be to use one that uses deterministic complexity models.

The idea of linking software complexity to software maintainability has been explored extensively by [[Meir M. Lehman|Professor Manny Lehman]], who developed his [[Lehman's laws of software evolution|Laws of Software Evolution]]. He and his co-author [[Les Belady]] explored numerous [[software metrics]] that could be used to measure the state of software, eventually concluding that the only practical solution is to use deterministic complexity models.<ref>MM Lehmam LA Belady; Program Evolution - Processes of Software Change 1985</ref>

==Types==

Associated with, and dependent on theThe complexity of an existing program, isdetermines the complexity associated withof changing the program. TheProblem complexity of a problem can be divided into two partscategories:<ref>[https://academia.edu.documents.s3.amazonaws.com/1811257/SHSM2011.pdf In software engineering, a problem can be divided into its accidental and essential complexity [1<nowiki>]</nowiki>.]</ref>

#'''Accidental complexity:''' Relatesrelates to difficulties a programmer faces due to the chosen software engineering tools. ASelecting a better fittingtool set of tools or a more highhigher-level programming language may reduce it. Accidental complexity is often alsoresults afrom consequence of the lack ofnot using the ___domain to frame the form of the solution i.e. the code.{{Citation needed|date=September 2015}} One[[Domain-driven practice thatdesign]] can help in avoidingminimize accidental complexity is [[___domain-driven design]].

#'''Essential complexity:''' Isis caused by the characteristics of the problem to be solved and cannot be reduced.

==Measures==

ManySeveral measures of software complexity have been proposed. Many of these, although yielding a good representation of complexity, do not lend themselves to easy measurement. Some of the more commonly used metrics are

* [[cyclomatic complexity|McCabe's cyclomatic complexity metric]]

* [[Halstead complexity measures|HalsteadsHalstead's software science metrics]]

* Henry and Kafura introduced "Software Structure Metrics Based on Information Flow" in 1981,<ref>Henry, S.; Kafura, D. IEEE Transactions on Software Engineering Volume SE-7, Issue 5, Sept. 1981 Page(s): 510 - 518</ref> which measures complexity as a function of "fan -in" and "fan -out". They define fan-in of a procedure as the number of local flows into that procedure plus the number of data structures from which that procedure retrieves information. Fan-out is defined as the number of local flows out of that procedure plus the number of data structures that the procedure updates. Local flows relate to data passed to, and from procedures that call or are called by, the procedure in question. Henry and Kafura's complexity value is defined as "the procedure length multiplied by the square of fan-in multiplied by fan-out" (Length ×(fan-in × fan-out)²).

* Chidamber and Kemerer introduced "A Metrics Suite for Object -Oriented Design" in 1994,<ref name=":0">Chidamber, S.R.; Kemerer, C.F. IEEE Transactions on Software Engineering Volume 20, Issue 6, Jun 1994 Page(s):476 - 493</ref> was introduced by Chidamber and Kemerer in 1994 focusing, as the title suggests, on metrics specifically for object -oriented code. They introduce six OO complexity metrics;: (1) weighted methods per class,; (2) coupling between object classes,; (3) response for a class,; (4) number of children,; (5) depth of inheritance tree; and (6) lack of cohesion of methods.

There are severalSeveral other metrics that can be used to measure programming complexity:

* Branching complexity (Sneed Metric)

* Data access complexity (Card Metric)

Line 14 ⟶ 22:

* Data flow complexity (Elshof Metric)

* Decisional complexity (McClure Metric)

*Path Complexity (Bang Metric)

[[Law of conservation of complexity|Tesler's Law]] is an [[adage]] in [[human–computer interaction]] stating that every [[Application software|application]] has an inherent amount of complexity that cannot be removed or hidden.

==Types==

Associated with, and dependent on the complexity of an existing program, is the complexity associated with changing the program. The complexity of a problem can be divided into two parts:<ref>[https://academia.edu.documents.s3.amazonaws.com/1811257/SHSM2011.pdf In software engineering, a problem can be divided into its accidental and essential complexity [1<nowiki>]</nowiki>.]</ref>

#Accidental complexity: Relates to difficulties a programmer faces due to the chosen software engineering tools. A better fitting set of tools or a more high-level programming language may reduce it. Accidental complexity is often also a consequence of the lack of using the ___domain to frame the form of the solution i.e. the code.{{Citation needed|date=September 2015}} One practice that can help in avoiding accidental complexity is [[___domain-driven design]].

#Essential complexity: Is caused by the characteristics of the problem to be solved and cannot be reduced.

==Chidamber and Kemerer Metrics==

{{Prose|date=August 2017}}

Chidamber and KemeberKemerer<ref name=":0" /> proposed a set of programing complexity metrics, widely used in many measurements and academic articles.: Theyweighted aremethods WMCper class, CBOcoupling between object classes, RFCresponse for a class, NOCnumber of children, DITdepth of inheritance tree, and LCOMlack of cohesion of methods, described below:

* WMC - weightedWeighted methods per class ("WMC")

** <math>WMC = \sum_{i=1}^nc_i</math>

** n is the number of methods on the class

** <math>c_i</math> is the complexity of the method

* CBO - couplingCoupling between object classes ("CBO")

** number of other class which is coupled (using or being used)

* RFC - responseResponse for a class ("RFC")

** <math>RFC = |RS|</math> where

** <math>RS = \{M\}\cup_{all\ i} \{R_i\}</math>

** <math>R_i</math> is set of methods called by method i

** <math>M</math> is the set of methods in the class

* NOC - numberNumber of children ("NOC")

** sum of all classes that inherit this class or a descendeddescendant of it

* DIT - depthDepth of inheritance tree ("DIT")

** maximum depth of the inheritance tree for this class

* LCOM- lackLack of cohesion of methods ("LCOM")

** Measures the intersection of the attributes used in common by the class methods

** <math>LCOM = \begin{cases} |P| - |Q|, & \text{if } |P| > |Q|

Line 44 ⟶ 50:

** Where <math>P = \{ (I_i,I_j)|I_i\cap I_j = \emptyset\}</math>

** And <math>Q = \{(I_i, I_j)|I_i \cap I_j \neq \emptyset\}</math>

** With <math>I_i</math> is the set of the attributes (instance variables) usedaccessed (read from or written to) by the nth<math>i</math>-th method of the class

==See also==

*[[Programming paradigm]]

*[[Software crisis]]

==References==

{{Reflist}}

==See also==

*[[Software crisis]] (and subsequent [[programming paradigm]] solutions)

*[[Software metric]]s - quantitative measure of some property of a program.

[[Category:Software metrics]]

[[Category:Complex systems theory]]